Schönhage-Strassen-Algorithmus

Der Schönhage-Strassen-Algorithmus basiert auf diskreter schneller Fourier-Transformation und ist im Sinne der Bitkomplexität auf mehrbändigen Turingmaschinen (maximale Laufzeit des Algorithmus gemessen als benötigte Bitoperationen in Abhängigkeit von der Bitlänge der Eingabegrößen) der effizienteste bislang bekannte Algorithmus zur Multiplikation zweier n-stelliger ganzer Zahlen.

Im Gegensatz zum "naiven" aus der Schule bekannten Algorithmus der Laufzeit $O\left(n^{2}\right)$ und dem 1962 entwickelten Karatsuba-Algorithmus mit einer Laufzeit von $O\left(n^{\log _{2}(3)}\right)$ terminiert dieser 1971 von Arnold Schönhage und Volker Strassen entwickelte Algorithmus bereits in $O{\Big (}n\cdot \log(n)\cdot \log {\big (}\log(n){\big )}{\Big )}$.

Bis heute konnte kein effizienterer Algorithmus gefunden werden. Als untere Schranke gibt es für den allgemeinen Fall nur die (triviale) lineare Laufzeit, an die sich der Algorithmus mit wachsender Zahlenlänge annähert. Allerdings haben die Forscher Hinweise dafür gefunden, dass die Schranke $O(n\cdot \log(n))$ niemals unterboten werden kann. Selbst bei modernen Computern ist diese Methode der Berechnung erst bei Zahlen mit mehreren tausend Stellen effizienter als der Karatsuba-Algorithmus. Dies liegt wohl allerdings weniger am Overhead des Schönhage-Strassen-Algorithmus, sondern vielmehr an der seit Jahrzehnten typischen Designoptimierung der Computerprozessoren, die dem Erreichen schneller Gleitkommaoperationen den Vorzug vor der Arithmetik in endlichen Restklassenringen ganzer Zahlen gibt.

Für die Suche nach den Algorithmen mit der besten (Zeit-) Komplexität in der Computer-Algebra genießt der Schönhage-Strassen-Algorithmus zentrale Bedeutung.

Weblinks

• Homepage von Prof. Dr. Arnold Schönhage
• Weltrekord-Rechenmethode kommt zu späten Ehren (Presseinformation der Universität Bonn vom 21. Dezember 2004)