Toom-Cook-Algorithmus

Der Toom-Cook-Algorithmus ist ein effizienter Algorithmus zur Multiplikation zweier ganzer Zahlen, der nach dem Prinzip Teile und herrsche arbeitet. Er wurde zuerst von Andrei Toom beschrieben, später durch Cook verbessert und in dessen Doktorarbeit veröffentlicht.

Er existiert in zwei Varianten. Die Variante mit fester Teilung besitzt eine Laufzeitkomplexität von $O \left(n^{1+\varepsilon} \right)$, wobei ε eine feste Konstante ist, die nur von der Teilung, aber nicht von der Eingabelänge n abhängt. Die Variante mit variabler Teilung besitzt Laufzeitkomplexität $O \left(n \cdot \log (n) \cdot 2^{\sqrt{2 \log(n)}}\right)$.

Der Algorithmus ist die Verallgemeinerung des Karatsuba-Algorithmus und deutlich schneller als der naive Algorithmus nach der Schulmethode (bzw. der russischen Bauernmultiplikation im Binärsystem), der Laufzeitkomplexität O(n²) besitzt. Für hinreichend große Zahlen ist er aber auch langsamer als der Schönhage-Strassen-Algorithmus, dessen Laufzeitkomplexität $O\Big(n \cdot \log(n) \cdot \log \big(\log(n) \big) \Big)$ beträgt und der aus Sicht der Komplexitätstheorie als schnellster, praktisch angewandter, Algorithmus zur Multiplikation ganzer Zahlen gilt.

Weblinks

• Doktorarbeit von Stephen Cook