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. The run-time bit complexity is, in Big O notation, 
, while the arithmetic complexity is 
. The algorithm uses Fast Fourier Transforms in rings with 
elements recursively. Knuth gives a full explanation of the method.
The Schönhage-Strassen algorithm is currently the asymptotically fastest multiplication method known. In practice it starts to outperform older methods such as Karatsuba multiplication for numbers beyond about 
(about 10,000 decimal digits).
[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.
