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 , wobei eine feste Konstante ist, die nur von der Teilung, aber nicht von der Eingabelänge 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 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, praktisch angewandter, Algorithmus zur Multiplikation ganzer Zahlen gilt.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.