imported>Cerotidinon: Untere statt obere Schranke ist hier interessant

2019-03-20T14:14:56Z

Untere statt obere Schranke ist hier interessant

Neue Seite

Der '''Toom-Cook-Algorithmus''' ist ein [[Effizienz (Informatik)|effizienter]] [[Algorithmus]] zur [[Multiplikation]] zweier [[Ganze Zahl|ganzer Zahlen]], der nach dem Prinzip ''[[Teile und herrsche (Informatik)|Teile und herrsche]]'' arbeitet. Er wurde zuerst von [[Andrei L. Toom|Andrei Toom]] beschrieben, später durch [[Stephen A. Cook|Cook]] verbessert und in dessen Doktorarbeit veröffentlicht.

Er existiert in zwei Varianten. Die Variante mit ''fester Teilung'' besitzt eine [[Zeitkomplexität|Laufzeitkomplexität]] von <math>O \left(n^{1+\varepsilon} \right)</math>, wobei <math>\varepsilon</math> eine feste Konstante ist, die nur von der Teilung, aber nicht von der Eingabelänge <math>n</math> abhängt. Die Variante mit ''variabler Teilung'' besitzt Laufzeitkomplexität <math>O \left(n \cdot \log (n) \cdot 2^{\sqrt{2 \log(n)}}\right)</math>.

Der Algorithmus ist die Verallgemeinerung des [[Karatsuba-Algorithmus]] und deutlich schneller als der naive Algorithmus nach der Schulmethode (bzw. der [[Russische Bauernmultiplikation|russischen Bauernmultiplikation]] im [[Dualsystem|Binärsystem]]), der Laufzeitkomplexität <math>\Theta(n^2)</math> besitzt. Für hinreichend große Zahlen ist er aber auch langsamer als der [[Schönhage-Strassen-Algorithmus]], dessen Laufzeitkomplexität <math> O\Big(n \cdot \log(n) \cdot \log \big(\log(n) \big) \Big)</math> beträgt und der aus Sicht der [[Komplexitätstheorie]] als schnellster, praktisch angewandter, Algorithmus zur Multiplikation ganzer Zahlen gilt.

== Weblinks ==

* [http://cr.yp.to/bib/1966/cook.html Doktorarbeit von Stephen Cook]

[[Kategorie:Zahlentheoretischer Algorithmus]]
[[Kategorie:Computerarithmetik]]
[[Kategorie:Multiplikation]]

Toom-Cook-Algorithmus - Versionsgeschichte

imported>Cerotidinon: Untere statt obere Schranke ist hier interessant