asymptotically fast Jacobi symbol
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).
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?
More information about the gmp-devel