New n log n algorithm for high-precision multiplication

[Niels Möller]

Vincent Lefevre <vincent at vinc17.net> 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, https://arxiv.org/abs/1205.2926, 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.

Regards,
/Niels

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