mpz_jacobi

[Niels Möller]

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:

  int
  mpn_jacobi_n (mp_ptr ap, mp_ptr bp, mp_size_t n, unsigned bits);

/nisse

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