mpz_jacobi

Niels Möller nisse at lysator.liu.se
Mon Apr 19 22:33:11 CEST 2010


I've now pushed in some new Jacobi code.

mpn_jacobi_lehmer: I think this is fairly solid, but with some code
duplication.

* div1 and div2 identical to those in hgcd2.c,

* mpn_hgcd2_jacobi almost the same as mpn_hgcd2 (but for performance
  this makes some sense. Benchmarking of jacobi vs gcd in the Lehmer
  range would be of some interest).

* mpn_jacobi_subdiv_step almost identical to mpn_gcd_subdiv_step and
  mpn_gcdext_subdiv_step. Since these are not performance critical, they
  should most likely be unified. There's also code in hgcd.c:hgcd_step
  which does something very similar.

* The basecase function mpn_jacobi_2 is longer and more complicated than
  I like. Maybe it can be simplified to eliminate some of the cases.

mpz_jacobi: The new code currently #if:ed out, it probably handles
jacobi of sizes n/1 and 1/n less efficiently than the old code.

I think it makes sense to do some cleanup and polishing on this code
before integrating the subquadratic jacobi variant.

To try the new code, enable it in mpz/jacobi.c, and also enable the extended
testing (check_large_quotients) in tests/mpz/t-jac.c.

Happy hacking,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.



More information about the gmp-devel mailing list