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 is O(N\cdot\log N\cdot\log\log N). The algorithm uses Fast Fourier Transforms in rings with 2^{2^n}+1 elements recursively. Donald Knuth[2] gives a full explanation of this method.

While this method is asymptotically the fastest multiplication method known[3], it is slower than classical methods such as Karatsuba multiplication in practice for numbers less than about 233,000.[4][5]

[edit] References

  1. ↑ A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), pp. 281–292.
  2. ↑ Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition), 1997. Addison-Wesley Professional, ISBN 0201896842.
  3. ↑ Rodney Van Meter and Kohei M. Itoh, "Fast quantum modular exponentiation", Physical Review A, Vol. 71 (2005).
  4. ↑  Overview of Magma V2.9 Features, arithmetic section: Discusses practical crossover points between varous algorithms.
  5. ↑  Chee Yap and Chen Li, QuickMul: Practical FFT-based Integer Multiplication, 2000.
  6. The book Fast Algorithms, ISBN 3411168919, describes both TP and TPAL.


Image:Mathapplied-stub_ico.png This applied mathematics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../s/c/h/Sch%C3%B6nhage-Strassen_algorithm_2782.html"
In other languages