Toom-Cook-Algorithmus

Der Toom-Cook-Algorithmus ist ein effizienter Algorithmus zur Multiplikation zweier ganzer Zahlen. Er existiert in zwei Varianten. Die Variante mit fester Teilung besitzt eine Laufzeitkomplexität von $O(n^{1+\epsilon )})$, wobei $\epsilon$ 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(n\cdot \log(n)\cdot 2^{\sqrt {2\log(n)}})$.

Der Algorithmus von Toom und Cook 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^{2})$ besitzt. Für hinreichend große Zahlen ist er aber auch langsamer als der Schönhage-Strassen-Algorithmus, dessen Laufzeitkomplexität $O(n\cdot \log(n)\cdot \log(\log(n)))$ beträgt und der aus Sicht der Komplexitätstheorie als schnellster bekannter Algorithmus zur Multiplikation ganzer Zahlen gilt.