Fürer's algorithm

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 Martin Fürer of Pennsylvania State UniversityFuhrer, 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] as an asymptotically less-complex algorithm than its predecessor, the Schönhage-Strassen algorithm published in 1971. [A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), pp. 281–292.]

The predecessor to the Fürer algorithm, the Schönhage-Strassen algorithm used fast Fourier transforms to compute integer products in time $O(n\; log\; n\; loglog\; n)$, and its authors, Arnold Schönhage and Volker Strassen, also conjectured a lower bound for the problem to be solved by an unknown algorithm as $O(n\; log\; n)$. Fürer's algorithm reduces the gap between these two bounds: it can be used to multiply binary integers of length "n" in time $n\; log\; n\; 2^\{O(log^*\; n)\}$ (or by a Boolean circuit with that many logic gates), where $log^*\; n$ represents the iterated logarithm operation. The difference between the $loglog\; n$ and $2^\{log^*\; n\}$ factors in the time bounds of the Schönhage-Strassen algorithm and the Fürer algorithm are so small that Fürer's algorithm would only speed up multiplication operations on "astronomically large numbers".

See also

* Number-theoretic transform

References

[http://www.cse.psu.edu/~furer/Papers/mult.pdf PDF download] .