# Fürer's algorithm

Jump to: navigation, search

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 Martin Fürer 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]

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]

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.[3]

In 2015 Harvey[4] proved that his optimized version of Fürer's algorithm 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. He also proposed a modification to Fürer's 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.[5] Nevertheless it remains just as impractical as all the other implementations of this algorithm.[6][7]

In 2016 Covanov and Thomé proposed an original multiplication algorithm of long integers based on the generalization of Fermat primes.[8]

## References

1. ^ a b M. Fürer (2007). "Faster Integer Multiplication" Proceedings of the 39th annual ACM Symposium on Theory of Computing (STOC), 55–67, San Diego, CA, June 11–13, 2007, and SIAM Journal on Computing, Vol. 39 Issue 3, 979–1005, 2009.
2. ^ A. Schönhage and V. Strassen (1971). "Schnelle Multiplikation großer Zahlen", Computing, Vol. 7, 281–292, 1971.
3. ^ A. De, C. Saha, P. Kurur and R. Saptharishi (2008). "Fast integer multiplication using modular arithmetic" Proceedings of the 40th annual ACM Symposium on Theory of Computing (STOC), 499–506, New York, NY, 2008, and SIAM Journal on Computing, Vol. 42 Issue 2, 685–699, 2013. arXiv:0801.1416
4. ^ D. Harvey, J. van der Hoeven and G. Lecerf (2015). "Even faster integer multiplication", February 2015. arXiv:1407.3360
5. ^ S. Covanov and E. Thomé (2015). "Fast arithmetic for faster integer multiplication", 2015.
6. ^ S. Covanov and E. Thomé (2014). "Efficient implementation of an algorithm multiplying big numbers", Internal research report, Polytechnics School, France, July 2014.
7. ^ S. Covanov and M. Moreno Mazza (2015). "Putting Fürer algorithm into practice", Master research report, Polytechnics School, France, January 2015.
8. ^ S. Covanov and E. Thomé (2016). "Fast integer multiplication using generalized Fermat primes", paper submitted to the Journal on Mathematics of Computation, January 2016. arXiv:1502.02800v2