Fürer's algorithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to 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] It is used in the Basic Polynomial Algebra Subprograms (BPAS) open source library.[3][4] The algorithm does not adapt for polynomials over finite fields.


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

Improved algorithms[edit]

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

In 2015, Harvey, Joris van der Hoeven and Lecerf[7] gave a new algorithm that achieves a running time of , making explicit the implied constant in the exponent. They also proposed a variant of their algorithm which achieves 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 . 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 .[12]

In March 2019, Harvey and van der Hoeven published the first integer multiplication algorithm, achieving what is conjectured to be the best asymptotic bound possible.[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[edit]


  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. ^ Schönhage, A.; Strassen, V. (1971). "Schnelle Multiplikation großer Zahlen" [Fast Multiplication of Large Numbers]. Computing (in German). 7 (3–4): 281–292. doi:10.1007/BF02242355. S2CID 9738629.
  3. ^ "FFT over large vectors >=2^16 -- FFT_test_exe test1 error in index · Issue #1 · orcca-uwo/BPAS". GitHub. Retrieved 4 September 2021.
  4. ^ Covanov, Sviatoslav; Mohajerani, Davood; Moreno-Maza, Marc; Wang, Lin-Xiao (2018-11-04). "Putting Fürer Algorithm into Practice with the BPAS Library". arXiv:1811.01490 [cs.SC].
  5. ^ 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
  6. ^ Lüders, Christoph (2015). Implementation of the DKSS Algorithm for Multiplication of Large Numbers (PDF). International Symposium on Symbolic and Algebraic Computation. pp. 267–274.
  7. ^ D. Harvey, J. van der Hoeven and G. Lecerf (2015). "Even faster integer multiplication", February 2015. arXiv:1407.3360
  8. ^ Covanov, S.; Thomé, E. (2015). "Fast Arithmetic for Faster Integer Multiplication". arXiv:1502.02800v1 [cs.SC]. Published as Covanov & Thomé (2019).
  9. ^ S. Covanov and E. Thomé (2014). "Efficient implementation of an algorithm multiplying big numbers", Internal research report, Polytechnics School, France, July 2014.
  10. ^ S. Covanov and M. Moreno Mazza (2015). "Putting Fürer algorithm into practice", Master research report, Polytechnics School, France, January 2015.
  11. ^ Covanov, Svyatoslav; Thomé, Emmanuel (2019). "Fast Integer Multiplication Using Generalized Fermat Primes". Math. Comp. 88 (317): 1449–1477. arXiv:1502.02800. doi:10.1090/mcom/3367. S2CID 67790860.
  12. ^ D. Harvey and J. van der Hoeven (2018). "Faster integer multiplication using short lattice vectors", February 2018. arXiv:1802.07932
  13. ^ Harvey, David; Van Der Hoeven, Joris (2019-04-12). "Integer multiplication in time O(n log n)". Annals of Mathematics.
  14. ^ Hartnett, Kevin (2019-04-14). "Mathematicians Discover the Perfect Way to Multiply". Wired. ISSN 1059-1028. Retrieved 2019-04-15.
  15. ^ Harvey, David; van der Hoeven, Joris (2021). "Integer multiplication in time O(n log n)". Annals of Mathematics. 193 (2): 563–617. doi:10.4007/annals.2021.193.2.4. ISSN 0003-486X. JSTOR 10.4007/annals.2021.193.2.4. S2CID 109934776.
  16. ^ Gilbert, Lachlan (4 April 2019). "Maths whiz solves 48-year-old multiplication problem". UNSW. Retrieved 18 April 2019.