New n log n algorithm for high-precision multiplication

[Vincent Lefevre]

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
reasons).

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 vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)