読者です 読者をやめる 読者になる 読者になる

SchemeでJacobi記号

誰の役に立つのか分からないけど. 分岐が意外と多い.
Jacobi記号はLegendre記号の一般化になっているので, Legendre記号もこれで求められますよ.

(define (Jacobi a n)
  (cond ((= a 0) 0)
        ((= a -1)
         (cond ((= (modulo n 4) 1) 1)
               ((= (modulo n 4) 3) -1)))
        ((= a 2)
         (cond ((= (modulo n 8) 1) 1)
               ((= (modulo n 8) 3) -1)
               ((= (modulo n 8) 5) -1)
               ((= (modulo n 8) 7) 1)))
        ((< a 0)
         (* (Jacobi (- a) n) (Jacobi -1 n)))
        ((= a 1) 1)
        ((>= a n)
         (Jacobi (modulo a n) n))
        ((even? a)
         (* (Jacobi (/ a 2) n) (Jacobi 2 n)))
        ((even? n)
         (Jacobi n a))
        (else
         (if (= 3 (modulo n 4) (modulo a 4))
             (- (Jacobi n a))
           (Jacobi n a)))))