New n log n algorithm for high-precision multiplication

[Niels Möller]

"Nelson H. F. Beebe" <beebe at math.utah.edu> writes:

> The noted numerical analyst, and multiple-precision arithmetic package
> author, David Bailey, has just posted a new article
>
> 	An n log(n) algorithm for multiplication
> 	https://mathscholar.org/2019/04/an-n-log-n-algorithm-for-multiplication/

Great recognition! I think David Harvey and Joris Van Der Hoeven have
worked on this for quite some time, chipping away at the log^* factor of
Fürer's algorithm in a series of papers. David is also a GMP
contributor.
 
> at his Math Scholar site.  It refers to a 42-page work of 18 March
> 2019 available at
>
> 	Integer multiplication in time O(n log n)
> 	David Harvey, Joris Van Der Hoeven
> 	https://hal.archives-ouvertes.fr/hal-02070778/document
>
> That archive is likely to be familiar to many gmp-devel list members,
> so perhaps their algorithm may already be implemented and tested in
> GMP.

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.

Regards,
/Niels

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