„Toom-Cook-Algorithmus“ – Versionsunterschied

Versionsgeschichte interaktiv durchsuchen

[ungesichtete Version]

[gesichtete Version]

Inhalt gelöscht Inhalt hinzugefügt

Inline

Aktuelle Version vom 20. März 2019, 16:14 Uhr

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 $O\left(n^{1+\varepsilon }\right)$ , wobei $\varepsilon$ 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\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 $\Theta (n^{2})$ besitzt. Für hinreichend große Zahlen ist er aber auch langsamer als der Schönhage-Strassen-Algorithmus, dessen Laufzeitkomplexität $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.

Weblinks

Doktorarbeit von Stephen Cook

@@ Zeile 1: / Zeile 1: @@
-Der '''Toom-Cook-Algorithmus''' ist ein [[Effizienz (Informatik)|effizienter]] [[Algorithmus]] zur [[Multiplikation]] zweier [[ganze Zahl|ganzer Zahlen]]. Er existiert in zwei Varianten. Die Variante mit ''fester Teilung'' besitzt eine [[Zeitkomplexität|Laufzeitkomplexität]] von <math>O(n^{1+\epsilon)})</math>, wobei <math>\epsilon</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(n \cdot \log (n) \cdot 2^{\sqrt{2 \log(n)}})</math>.
+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 von [[Andrei. L. Toom|Toom]] und [[Stephen A. Cook|Cook]] ist die Verallgemeinerung des [[Karatsuba-Algorithmus]] und deutlich schneller als der naive Algorithmus nach der Schulmethode (bzw. der [[russische Bauernmultiplikation|russischen Bauernmultiplikation]] im [[Binärsystem]]), der Laufzeitkomplexität <math>O(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(n \cdot \log(n) \cdot \log(\log(n)))</math> beträgt und der aus Sicht der [[Komplexitätstheorie]] als schnellster bekannter Algorithmus zur Multiplikation ganzer Zahlen gilt.
+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]]