Thanks everyone for the suggestions, they will be incorporated. Felleisen: Wie geht's? Your version is very nice, thank you for the improvements.
Soegaard: I'll write a pull request soon. Thank you. As for the Legendre symbol, I believe it's already implemented <http://docs.racket-lang.org/math/number-theory.html?q=number-theory#%28def._%28%28lib._math%2Fnumber-theory..rkt%29._quadratic-character%29%29> as quadratic-character. Maybe an alias or renaming is in order? Oh, P.S. Since we have Legendre and Jacobi, I figured "why not complete the set?" and wrote a Kronecker symbol <http://mathworld.wolfram.com/KroneckerSymbol.html> implementation too. It seems correct on various test vectors but I'm having trouble getting it to typecheck. Once I figure it out I could file another PR. On Fri, Sep 11, 2015 at 9:57 AM, Matthias Felleisen <[email protected]> wrote: > > 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/CAPASY%3DU3wwZOfVfm0%3D8aXdkac0ZJtAagYf39Bi%3DYD8fDdgSdFQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
