Schönhage-Strassen algorithm

From Wikipedia, the free encyclopedia

In mathematics, the Schönhage-Strassen algorithm is an asymptotically fast method for multiplication of large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971^[1]. The run-time bit complexity is, in Big O notation, $O(N\cdot\log N\cdot\log\log N)$ , while the arithmetic complexity is $O(N \cdot \log N)$ ^[2]. The algorithm uses Fast Fourier Transforms in rings with $2^{2^n}+1$ elements recursively. Knuth^[3] gives a full explanation of the method.

The Schönhage-Strassen algorithm is currently the asymptotically fastest multiplication method known^[4]. In practice it starts to outperform older methods such as Karatsuba multiplication for numbers beyond about $2^{2^{15}}+1$ (about 10,000 decimal digits).^[5]^[6]

[edit] References

^ A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), pp. 281–292.
^ Peter Bürgisser, Michael Clausen and Amin Shokrollahi, Algebraic Complexity Theory, 1997. Springer-Verlag, ISBN 3540605827.
^ Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition), 1997. Addison-Wesley Professional, ISBN 0201896842.
^ Rodney Van Meter and Kohei M. Itoh, "Fast quantum modular exponentiation", Physical Review A, Vol. 71 (2005).
^ Overview of Magma V2.9 Features, arithmetic section: Discusses practical crossover points between various algorithms.
^ Chee Yap and Chen Li, QuickMul: Practical FFT-based Integer Multiplication, 2000.
^ Michael T. Goodrich and Roberto Tamassia Algorithm Design Foundations, Analysis, and Internet Examples. Gives an Introduction to FFT with an Java Implementation of the QuickMul Algorithm. Might be a good reference for expanding the article.