New n log n algorithm for high-precision multiplication

Vincent Lefevre vincent at
Mon Apr 15 09:04:32 UTC 2019

On 2019-04-15 10:22:02 +0200, Niels Möller wrote:
> No, current GMP FFT multiplication is based on Schönhage-Strassen.
> There's also unfinished work on small-prime FFT, motivated mainly to get
> better cache locality (for huge numbers, field elements in
> Schönhage-Strassen get so large that they exceed the L1 cache, slowing
> down the supposedly very efficient field operations).
> It still seems unclear how useful the new n log n algorithm will be for
> practical implementation. I've had a quick read of the two papers, and
> as I understood it, the authors propose two different n log n algorithms
> for integer multiplication and one for polynomial multiplication. Of the
> two integer algorithms, one has a strict unconditional proof, while the
> other depends on some conjecture on prime distribution, but may be more
> useful for implementation in practice.

IMHO, the interest is just theoretical, unless the new algorithms
*also* allow one to gain some constant factor hidden by the O(),
but in general, for asymptotically faster algorithms, this is not
the case. Even concerning the full Schönhage-Strassen algorithm,
I have some doubt on whether it is really interesting compared to
variants that would be limited to not too huge values of n (which
could not be supported due to other limitations in GMP or other

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.

Vincent Lefèvre <vincent at> - Web: <>
100% accessible validated (X)HTML - Blog: <>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)

More information about the gmp-devel mailing list