asymptotically fast Jacobi symbol
Paul Zimmermann
Paul.Zimmermann at loria.fr
Sat Jan 23 20:05:41 CET 2010
> this is not completely correct. As demonstrated on
> http://www.loria.fr/~zimmerma/mca/pub226.html, our right-to-left algorithm
> is 6.3% faster than mpz_gcd for 10^8 limbs.
>
> Is that because a certain efficiency of the gcd algorithm for 10^8
> limbs, or is it perhaps due to non-linearity of the underlying
> multiplication?
my guess is that it is due to a different way of implementing the "half-gcd"
algorithm: one can either return both the corresponding 2x2 matrix and the
new remainders (which I guess mpz_gcd currently does) or only return the
matrix, and recompute the new remainders when needed (which my implementation
of the binary gcd does).
> Or are you saying the bgcd is now superior to ngcd?
no, just that my implementation if bgcd is asymptotically faster to that of
ngcd in GMP. I believe with the same kind of implementation, ngcd should beat
bgcd by about 5%.
> > Which algorithm do you expect to be fastest for Jacobi symbol
> > computation, one based on ngcd, or your present suggestion?
>
> I have no definite answer to that. You need to implement one
> based on ngcd and compare.
>
> Does it suffer from the same inherent growth-to-the-left problem as the
> gcd algorithm?
yes (for the right-to-left variant).
Paul
More information about the gmp-devel
mailing list