# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# 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 $2^{2^n}+1$ 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.