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
* 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.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel