New n log n algorithm for high-precision multiplication

Niels Möller nisse at
Mon Apr 15 09:55:23 UTC 2019

Vincent Lefevre <vincent at> writes:

> For instance, about the conjecture on prime distribution, I suppose
> that it matters only when considering n going to the infinity, but
> in practice, n remains bounded.

For variants of small-prime FFT, one would want primes that fit in a
machine word and are of the form c 2^k + 1 with smallish c, to get roots
of unity of high power-of-two order. (And to take advantage of David
Harvey's trick,, one would need primes
of size 63 bits rather than 64). And then there's a definite finite number
of suitable primes, regardless of any conjectures.

I doubt going to primes larger than a machine word will bring practical
speedup, even if it's essential for theoretical asymptotic performance.


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

More information about the gmp-devel mailing list