nisse at lysator.liu.se
Fri May 20 21:19:35 CEST 2011
nisse at lysator.liu.se (Niels Möller) writes:
> I've now pushed in some new Jacobi code.
> I think it makes sense to do some cleanup and polishing on this code
> before integrating the subquadratic jacobi variant.
I've just pushed in subquadratic jacobi code. For larger sizes
(1000-10000 limbs) it seems to be about 1% slower than gcd (and still
maybe 5% slower for sizes up to 100 limbs). It uses the same thresholds
as the gcd code (GCD_DC_THRESHOLD and HGCD_DC_THRESHOLD), I doubt it
will make any significant difference to tune these separately (although
there surely is a small difference in the linear term).
To get code duplication to a more manageable level, I first reorganized
hgcd a bit, and generalized the mpn_gcd_subdiv_step so that it can be
used by hgcd.
Counting the number on non-comment lines in mpn/generic relating to gcd
and jacobi (*gcd*.c *jac*.c), there were 2115 lines in gmp-5.0.2, and
3389 in the version I just pushed in.
The mpn interface is currently:
mpn_jacobi_n (mp_ptr ap, mp_ptr bp, mp_size_t n, unsigned bits);
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel