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

• Schönhage's TP page with short introduction, samples and download link

References

• The book Fast Algorithms, ISBN 3411168919, describes both TP and TPAL.