Fürer's algorithm

Fürer's algorithm is an integer multiplication algorithm for extremely large integers with very low asymptotic complexity. It was published in 2007 by the Swiss mathematician of Pennsylvania State University^[1] as an asymptotically faster algorithm when analysed on a multitape Turing machine than its predecessor, the Schönhage–Strassen algorithm.^[2] It is used in the Basic Polynomial Algebra Subprograms (BPAS) open source library.^[3][4]

Background[]

The Schönhage–Strassen algorithm uses the fast Fourier transform (FFT) to compute integer products in time ${\displaystyle O(n\log n\cdot \log \log n)}$ and its authors, Arnold Schönhage and Volker Strassen, conjecture a lower bound of ${\displaystyle \Omega (n\log n)}$. Fürer's algorithm reduces the gap between these two bounds. It can be used to multiply integers of length ${\displaystyle n}$ in time ${\displaystyle O\left(n\log n\ \cdot 2^{O(\log ^{*}n)}\right)}$ where log*n is the iterated logarithm. The difference between the ${\displaystyle \log \log n}$ and ${\displaystyle 2^{\log ^{*}n}}$ terms, from a complexity point of view, is asymptotically in the advantage of Fürer's algorithm for integers greater than ${\displaystyle 2^{2^{64}}}$. However the difference between these terms for realistic values of ${\displaystyle n}$ is very small.^[1]

Improved algorithms[]

In 2008 De et al gave a similar algorithm which relies on modular arithmetic instead of complex arithmetic to achieve in fact the same running time.^[5] It has been estimated that it becomes faster than Schönhage-Strassen for inputs exceeding a length of ${\displaystyle 10^{10^{4796}}}$.^[6]

In 2015 Harvey, Joris van der Hoeven and Lecerf^[7] gave a new algorithm that achieves a running time of ${\displaystyle O(n\log n\cdot 2^{3\log ^{*}n})}$ making explicit the implied constant in the ${\displaystyle O(\log ^{*}n)}$ exponent. They also proposed a variant of their algorithm which achieves ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$ but whose validity relies on standard conjectures about the distribution of Mersenne primes.

In 2015 Covanov and Thomé provided another modification of Fürer's algorithm which achieves the same running time.^[8] Nevertheless, it remains just as impractical as all the other implementations of this algorithm.^[9][10]

In 2016 Covanov and Thomé proposed an integer multiplication algorithm based on a generalization of Fermat primes that conjecturally achieves a complexity bound of ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$. This matches the 2015 conditional result of Harvey, van der Hoeven, and Lecerf but uses a different algorithm and relies on a different conjecture.^[11]

In 2018 Harvey and van der Hoeven used an approach based on the existence of short lattice vectors guaranteed by Minkowski's theorem to prove an unconditional complexity bound of ${\displaystyle O(n\log n\cdot 2^{2\log ^{*}n})}$.^[12]

In March 2019, Harvey and van der Hoeven published a long-sought after ${\displaystyle O(n\log n)}$ integer multiplication algorithm, which is conjectured to be asymptotically optimal.^[13][14][15] Because Schönhage and Strassen predicted that n log(n) is the ‘best possible’ result Harvey said: “...our work is expected to be the end of the road for this problem, although we don't know yet how to prove this rigorously.”^[16]

See also[]

• Galactic algorithm
• Number-theoretic transform

References[]