New n log n algorithm for high-precision multiplication
nisse at lysator.liu.se
Mon Apr 15 09:55:23 UTC 2019
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.
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel