Fürer's algorithm is an integer multiplication algorithm for very large numbers possessing a very low asymptotic complexity. It was created in 2007 by Swiss mathematician Martin Fürer of Pennsylvania State University as an asymptotically faster (when analysed on a multitape Turing machine) algorithm than its predecessor, the Schönhage–Strassen algorithm published in 1971.
The predecessor to the Fürer algorithm, the Schönhage-Strassen algorithm, used fast Fourier transforms to compute integer products in time in big O notation and its authors, Arnold Schönhage and Volker Strassen, also conjectured a lower bound for the problem of . Here, denotes the total number of bits in the two input numbers. Fürer's algorithm reduces the gap between these two bounds: it can be used to multiply binary integers of length in time (or by a circuit with that many logic gates), where log*n represents the iterated logarithm operation. However, the difference between the and factors in the time bounds of the Schönhage-Strassen algorithm and the Fürer algorithm for realistic values of is very small.
See also 
- Fürer, M. (2007). "Faster Integer Multiplication" in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11–13, 2007, San Diego, California, USA
- A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), pp. 281–292.
- Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Fast Integer Multiplication Using Modular Arithmetic. Symposium on Theory of Computation (STOC) 2008. arXiv:0801.1416
|This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|