Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

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 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 .

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 beträgt und der aus Sicht der Komplexitätstheorie als schnellster bekannter Algorithmus zur Multiplikation ganzer Zahlen gilt.

Weblink

• Doktorarbeit von Stephen Cook

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Toom-Cook-Algorithmus, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.