FLINT has a new, faster, integer GCD. Adapt for mpz_gcd()?

[Torbjörn Granlund]

[Fredrik Johansson <fredrik.johansson at gmail.com> trimmed from the
recipient list, gmail.com rejects mail from GMP.]


Fredrik Johansson <fredrik.johansson at gmail.com> writes:

  To clarify: FLINT has a port of GMP's GCD code (all credit to the GMP team)
  with only some small tweaks to the actual GCD algorithm.

  The speedup (~1.1x for small operands, 2-3x for large ones; slightly more
  multithreaded) derives almost entirely from FLINT's faster integer
  multiplication (tables of straight-line NxM kernels for schoolbook
  multiplication,

How large is your mul_basecase replacement?  I would assume it could
became several megabytes if all schoolbook range size combination would
get their own straight line code.

  small-prime FFT above a couple hundred limbs)

I and Niels wrote small prime multiplication code for GMP 15 years ago.
But we never made the final touches for integration in GMP.

I don't recall to have seen 2-3x speedup, though, except perhaps for
truly astronomical operand sizes where the current GMP code has close to
100% cache misses, while our new code had close to 100% cache hit.


-- 
Torbjörn
Please encrypt, key id 0xC8601622