Adding Jacobi symbols to math/number-theory

[eu90h]

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.

[Robby Findler]

On line 7, the call to raise-argument-error should be:

(raise-argument-error 'jacobi "odd?" 1 a n)

This also speaks to the need for contracts plus types!

Robby

> --
> 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 racket-dev+...@googlegroups.com.
> To post to this group, send email to racke...@googlegroups.com.
> 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]

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

--

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 racket-dev+...@googlegroups.com.
To post to this group, send email to racke...@googlegroups.com.
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

[Matthias Felleisen]

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))

> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-dev/CABefVgzpmfW7pieTs8cVaKbNwXZHVnhpjG6bTP6gHtg%3DJ0QenQ%40mail.gmail.com.

[Stefan A]

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 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 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.

[Jens Axel Søgaard]

2015-09-12 6:38 GMT+02:00 Stefan A <eule...@gmail.com>:

Soegaard: I'll write a pull request soon. Thank you. 

As for the Legendre symbol, I believe it's already implemented as quadratic-character. Maybe an alias or renaming is in order?

I had forgotten quadratic-character existed.

 

Oh, P.S. 

Since we have Legendre and Jacobi, I figured "why not complete the set?" and wrote a Kronecker symbol 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.

Great.

/Jens Axel