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 University as an asymptotically less-complex 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 $O(n\log n\log \log 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)$. Here, n 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 n in time $n\log n2^{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 $\log \log 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

PDF download.