asymptotically fast Jacobi symbol
Torbjorn Granlund
tg at gmplib.org
Sat Jan 23 14:29:06 CET 2010
Paul Zimmermann <Paul.Zimmermann at loria.fr> writes:
GMP 5.0.0 implements a quadratic algorithm for the Jacobi symbol. In
http://wwwmaths.anu.edu.au/~brent/pub/pub236.html we describe a subquadratic
algorithm, and exhibit speedups of almost a factor of 100 over GMP (which is
very difficult to achieve).
Nice work!
I don't understand your comment about difficultly of 100x speedup.
Surely 100x is not difficult to achieve when comparing a O(n^2)
algorithm with a O(M(n)log(n)) algorithm?
For 10^9 limbs, GMP's asymptotically fastest multiplication is about
1,000,000 times faster that GMP's schoolbook multiplication...
When comparing the fast GCD algorithms, Niels' ngcd is the current
champion. Your and Stehlé's right-to-left algorithm is unfortunately
slower. (I write unfortunately since its relative simplicity is a great
advantage from an implementation perspective.)
Which algorithm do you expect to be fastest for Jacobi symbol
computation, one based on ngcd, or your present suggestion?
--
Torbjörn
More information about the gmp-devel
mailing list