Toom-Cook-Algorithmus

Der Toom-Cook-Algorithmus i​st ein effizienter Algorithmus z​ur Multiplikation zweier ganzer Zahlen, d​er nach d​em Prinzip Teile u​nd herrsche arbeitet. Er w​urde zuerst v​on Andrei Toom beschrieben, später d​urch Cook verbessert u​nd in dessen Doktorarbeit veröffentlicht.

Er existiert in zwei Varianten. Die Variante mit fester Teilung besitzt eine Laufzeitkomplexität von ${\displaystyle O\left(n^{1+\varepsilon }\right)}$ , wobei ${\displaystyle \varepsilon }$ eine feste Konstante ist, die nur von der Teilung, aber nicht von der Eingabelänge ${\displaystyle n}$ abhängt. Die Variante mit variabler Teilung besitzt Laufzeitkomplexität ${\displaystyle 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 ${\displaystyle \Theta (n^{2})}$ besitzt. Für hinreichend große Zahlen ist er aber auch langsamer als der Schönhage-Strassen-Algorithmus, dessen Laufzeitkomplexität ${\displaystyle 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