New n log n algorithm for high-precision multiplication
Niels Möller
nisse at lysator.liu.se
Mon Apr 15 08:22:02 UTC 2019
"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.
More information about the gmp-devel
mailing list