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