Science Fair Project Encyclopedia
Schönhage-Strassen algorithm
In mathematics, the Schönhage-Strassen algorithm is an asympotically fast method for multiplication of large integer numbers. It was developed by Arnold Schönhage and Volker Strassen and published in Computing 7 (1971), 281-292. The run-time is O(N log N log log N). The algorithm uses Fast Fourier Transforms in rings with 
elements recursively. A good explanation can be found in Donald Knuth's The Art of Computer Programming, Volume 2, 3rd ed., pp. 306-311, ISBN 0201896842.
Schönhage designed and implemented together with Andreas F. W. Grotefeld and Ekkehard Vetter a multitape Turing machine, called TP, in software. The machine is programmed in TPAL , an assembler language. They implemented numerous numerical algorithms including the Schönhage-Strassen algorithm on this machine.
External links
References
- The book Fast Algorithms, ISBN 3411168919, describes both TP and TPAL.
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details