May I propose a few small Racket-style improvements? Otherwise follow Jens's
suggestions and
#lang typed/racket
(provide
;; coming to a Typed Racket near you soon
#;
[jacobi-symbol (-> non-negative-integer? (and/c non-negative-integer? odd?)
integer?)]
jacobi-symbol)
;;
------------------------------------------------------------------------------------
(require math/number-theory)
(module+ test
(require typed/rackunit))
(: jacobi-symbol (-> Nonnegative-Integer Positive-Integer Integer))
(define (jacobi-symbol a n)
(unless (odd? n)
(raise-argument-error 'jacobi "odd?" 1 a n))
(cond
[(= n 1) 1]
[else
(define prime-factors (factorize n))
(let next ([factor (first prime-factors)] [remaining-factors (rest
prime-factors)])
(define p (first factor))
(define e (second factor))
(define qcap (quadratic-character a p))
(if (null? remaining-factors)
(expt qcap e)
(* (expt qcap e) (next (first remaining-factors) (rest
remaining-factors)))))]))
(module+ test
(check-equal? (jacobi-symbol 0 23) 0)
(check-equal? (jacobi-symbol 1 1) 1)
(check-equal? (jacobi-symbol 2 1) 1)
(check-equal? (jacobi-symbol 4 1) 1)
(check-equal? (jacobi-symbol 2 3) -1)
(check-equal? (jacobi-symbol 4 5) 1)
(check-equal? (jacobi-symbol 7 5) -1)
(check-equal? (jacobi-symbol 5 3) -1)
(check-equal? (jacobi-symbol 25 53) 1)
(check-equal? (jacobi-symbol 21 1) 1)
(check-equal? (jacobi-symbol 21 21) 0)
(check-equal? (jacobi-symbol 12 3) 0)
(check-equal? (jacobi-symbol 30 59) -1)
(check-equal? (jacobi-symbol 7 51) -1)
(check-equal? (jacobi-symbol 22 55) 0))
On Sep 11, 2015, at 9:40 AM, Jens Axel Søgaard <[email protected]> wrote:
> This makes a very nice addition.
>
> Write a few lines as documentation:
>
>
> https://github.com/racket/math/blob/master/math-doc/math/scribblings/math-number-theory.scrbl
>
> Move the tests to:
>
>
> https://github.com/racket/math/blob/master/math-test/math/tests/number-theory-tests.rkt
>
> Send a PR at Github.
>
>
> If you have time consider adding the Legendre symbol at the same time?
>
> http://mathworld.wolfram.com/LegendreSymbol.html
>
> /Jens Axel
>
>
> 2015-09-11 11:59 GMT+02:00 eu90h <[email protected]>:
> Hello,
>
> I wrote a small procedure computing the Jacobi symbol. I thought it might be
> cool/useful to put in the math/number-theory pkg if possible.
> The procedure is contained in this gist, along with some test vectors.
>
> Thanks.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/racket-dev/8a0ab0ad-5b76-4db6-b3be-d26f2e1cb4b3%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>
>
>
> --
> --
> Jens Axel Søgaard
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Racket Developers" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/racket-dev/CABefVgzpmfW7pieTs8cVaKbNwXZHVnhpjG6bTP6gHtg%3DJ0QenQ%40mail.gmail.com.
> For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
"Racket Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/racket-dev/4DF0C25A-1D62-49B7-ACE8-F1B020E3587E%40ccs.neu.edu.
For more options, visit https://groups.google.com/d/optout.
