New n log n algorithm for high-precision multiplication
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
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
> 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
> That archive is likely to be familiar to many gmp-devel list members,
> so perhaps their algorithm may already be implemented and tested in
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.
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel