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 , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon} eine feste Konstante ist, die nur von der Teilung, aber nicht von der Eingabelänge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} abhängt. Die Variante mit variabler Teilung besitzt Laufzeitkomplexität Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\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.
