Quelltext der Seite Karazuba-Algorithmus

Der '''Karazuba-Algorithmus''' ist ein [[Algorithmus]] zur [[Multiplikation]] zweier großer [[Ganze Zahl|ganzer Zahlen]]. Er wurde 1960 von dem 23-jährigen [[Anatoli Alexejewitsch Karazuba]] entwickelt und 1962 veröffentlicht.

Bezeichnet <math>n</math> die [[Bit]]-Anzahl der beiden Zahlen und <math>O</math> ein [[Landau-Symbole|Landau-Symbol]], so ist der Algorithmus mit einer [[Zeitkomplexität|Laufzeitkomplexität]] von <math>O(n^{\log_2 3}),\ \log_2 3=1{,}5849\ldots ,</math> deutlich schneller als die Schulmethode. Diese (und auch deren implizite Übertragung auf das [[Dualsystem|Binärsystem]] in Form der [[Russische Bauernmultiplikation|russischen Bauernmultiplikation]]) besitzt eine Laufzeitkomplexität von <math>O(n^2)</math>. Die Methode von Karazuba wurde zum Vorbild für das [[Teile und herrsche (Informatik)|Teile-und-herrsche-Prinzip]] in der Informatik. Für hinreichend große Zahlen ist der Karazuba-Algorithmus langsamer als seine Verallgemeinerungen, wie der [[Toom-Cook-Algorithmus]] (1965) und der [[Schönhage-Strassen-Algorithmus]] (1971), dessen Laufzeitkomplexität <math>O\big(n (\log n) \log (\log n)\big)</math> beträgt und der aus Sicht der [[Komplexitätstheorie]] als schnellster Algorithmus zur Multiplikation großer ganzer Zahlen galt, bis 2007 [[Martin Fürer]] eine Weiterentwicklung mit einer (bisher nur theoretisch) geringeren Laufzeitkomplexität vorstellte.<ref>Das englische Lemma [[:en:Fürer's algorithm|Fürer's algorithm]] enthält dazu einige Hinweise.</ref>

== Idee des Algorithmus ==

Multiplizieren verursacht in der Schulmethode einen Aufwand, der mit dem Quadrat der Stellenanzahl wächst, während [[Addition]]en und [[Logische Verschiebung|Verschiebeoperationen]], bei denen mit einer Potenz der Basis des verwendeten [[Stellenwertsystem]]s multipliziert wird, nur linearen Aufwand benötigen. Die Idee ist, nach dem Teile-und-herrsche-Prinzip die beiden zu multiplizierenden Zahlen in zwei Teile aufzuspalten, und die Multiplikationen soweit möglich durch Additionen und Verschiebeoperationen zu ersetzen. Das Ausmultiplizieren der aufgeteilten Zahlen ergibt drei Teilterme, die durch vier Multiplikationen gebildet werden. Diese können durch Verschiebe- und Additionsoperationen zum Gesamtergebnis zusammengesetzt werden. Einer dieser Terme ist dabei eine Summe zweier Produkte. Dieser Term lässt sich als Differenz mit einem neuen Produkt und der Summe der anderen beiden Teilterme schreiben. Insgesamt spart man so also eine Teilmultiplikation ein. Führt man dieses Verfahren [[Rekursion|rekursiv]] durch, so erhält man eine wesentlich günstigere Laufzeit als nach der Schulmethode.

== Der Algorithmus im Detail ==

Der hier angegebene Algorithmus gilt für [[Natürliche Zahl|natürliche Zahlen]]. Er lässt sich aber leicht auch auf ganze Zahlen verallgemeinern, indem ihre [[Vorzeichen (Zahl)|Vorzeichen]] gesondert berücksichtigt werden.
Die Faktoren <math>X</math> und <math>Y</math> seien im Stellenwertsystem zur Basis <math>b</math> als [[Tupel]] dargestellt. Der Wert von <math>b</math> ist unerheblich: Etwa in einem [[Computer]] mit einem [[Multiplizierer (Digitaltechnik)|Multiplizierer]] für 32 Bit breite Zahlen würde <math>b=2^{31}</math> gewählt werden. Die Beispiele weiter unten verwenden [[Dezimalsystem|Dezimalzahlen]]. Um die Rekursion bis <math>n=1</math> durchführen zu können, seien die Längen beider Zifferntupel eine Zweierpotenz <math>2^m</math> mit <math>m>1</math>, und es sei <math>n:\,=2^{m-1}</math>. Das ist immer erreichbar durch geeignet vorangestellte Nullen; an der unten durchgeführten Laufzeitabschätzung ändert sich dadurch nichts Wesentliches.

Die Zifferntupel seien also
:<math>X = (x_{2n-1}\ldots x_0)_b\ </math> und <math>\ Y = (y_{2n-1}\ldots y_0)_b.</math>
Jedes Zifferntupel wird nun in zwei Tupel der Länge <math>n</math> aufgespalten. Das liefert die vier Zahlen
:<math>X_h = (x_{2n-1}\ldots x_n)_b\ </math> und <math>\ X_l = (x_{n-1}\ldots x_0)_b\ </math> sowie
:<math>Y_h = (y_{2n-1}\ldots y_n)_b\ </math> und <math>\ Y_l = (y_{n-1}\ldots y_0)_b.</math>
Damit ist
:<math>X = X_h b^n + X_l\ </math> und <math>\ Y = Y_h b^n + Y_l.</math>
Ausmultipliziert ergibt sich
:<math>X\,Y = (X_h b^n + X_l) (Y_h b^n + Y_l) = X_h Y_h b^{2n} + (X_h Y_l + X_l Y_h)\, b^n + X_l Y_l.</math>

Den Term <math>X_h Y_l + X_l Y_h</math> kann man nun in eine andere, hier schneller [[Berechenbarkeit|berechenbare]] Form bringen:
:<math>X_h Y_l + X_l Y_h = (X_h Y_h + X_h Y_l + X_l  Y_h + X_l Y_l) - (X_h Y_h + X_l Y_l)=  (X_h + X_l) (Y_h + Y_l) - (X_h Y_h + X_l Y_l).</math>

Damit ergibt sich für das Produkt die Darstellung
:<math>X\,Y = X_h Y_h b^{2n} + \big((X_h + X_l) (Y_h + Y_l) - (X_h Y_h + X_l Y_l)\big)\, b^n + X_l Y_l,</math>

in der nur noch die drei „kurzen“ Produkte
:<math>P_1 = X_h Y_h,\ P_2 = X_l Y_l,\ P_3 = (X_h + X_l) (Y_h + Y_l)</math>

erscheinen. Rekursiv berechnet und mit einfachen Verschiebe- und Additionsoperationen verknüpft, ergeben sie
:<math>X\,Y = P_1 b^{2n} + \big(P_3 - (P_1 + P_2)\big)\, b^n + P_2.</math>

Von den vier möglichen Produkten (von X mit Y) X<sub>h</sub> Y<sub>h</sub>, X<sub>h</sub> Y<sub>l</sub>, X<sub>l</sub> Y<sub>h</sub>, X<sub>l</sub> Y<sub>l</sub> wird das erste P<sub>1</sub> und das letzte P<sub>2</sub> direkt im Ergebnis verwendet. Der Term aus der Summe der beiden mittleren Produkten kann als Summe von allen Produkten minus des ersten und letzten Produkt gebildet werden. Die Summe aus allen vier Produkten kann über das neu eingeführte Produkt P<sub>3</sub> mit nur einer Multiplikation erzeugt werden.

== Laufzeitanalyse ==

Eine Multiplikation zweier <math>2n</math>-stelliger Zahlen wird zurückgeführt auf drei Multiplikationen von je zwei <math>n</math>-stelligen Zahlen und vier Additionen bzw. Subtraktionen <math>n</math>-stelliger Zahlen eventuell mit Überträgen sowie mit zwei Verschiebungen. Die benötigte Zeit für die Operationen, die keine Multiplikationen sind, ist kleiner als <math>cn</math> mit einer von <math>n</math> unabhängigen Konstanten <math>c</math>. Bezeichnet <math>T(s)</math> die Gesamtzahl der Operationen bei der Multiplikation zweier <math>s</math>-stelliger Zahlen, so gilt

:<math>T(2n) \le 3T(n) + cn,\ T(1)=1.</math>

Der hier anwendbare erste Fall des [[Master-Theorem]]s mit <math>a=3,\ b=2</math> und <math>f(n)\le cn</math> liefert <math>O(n^{\log_2 3})</math> als Laufzeitkomplexität von <math>T(n).</math>
Die direkte Herleitung mit [[Vollständige Induktion|vollständiger Induktion]] ermöglicht einen genaueren Einblick:
:<math>T(2^m)\le 3^mT(1)+\frac{c}{2}2^m\sum\limits_{k=0}^{m-1}\left(
\frac{3}{2}\right)^k=3^m+c (3^m-2^m)<(c+1)\,3^m.</math>

Ersetzen von <math>2^m</math> durch <math>n</math> ergibt dann

:<math>T(n) < (c+1)\,(2^{\log_2 3})^m = (c+1)\,(2^m)^{\log_2 3} = (c+1)\,n^{\log_2 3}.</math>

== Beispiel zur Produktumformung ==

Die zu multiplizierenden Zahlen seien

:<math>X = 84\,232\,332\,233\ </math> und <math>\ Y = 1\,532\,664\,392</math>.

Da es hier nur um die Veranschaulichung der Produktumformung geht, wird mit vorangestellten Nullen auf die nächste gerade und gleiche Länge und nicht auf eine Zweipotenzlänge aufgefüllt. Damit ergeben sich die Zifferntupel
:<math>X = {\color{Blue}084\,232}\,{\color{OliveGreen}332\,233}</math> und <math>Y = {\color{Red}001\,532}\,{\color{Brown}664\,392}</math>
der Länge <math>2n = 12</math>, die in vier Tupel der Länge <math>n = 6</math> zerlegt werden:
:<math>X_h = {\color{Blue}084\,232}</math> und <math>X_l = {\color{OliveGreen}332\,233}</math> sowie
:<math>Y_h = {\color{Red}001\,532}</math> und <math>Y_l = {\color{Brown}664\,392}.</math>
Es gilt
:<math>X = X_h \cdot 10^6 + X_l = {\color{Blue}084\,232} \cdot 10^6 + {\color{OliveGreen}332\,233}</math> und
:<math>Y = Y_h \cdot 10^6 + Y_l = {\color{Red}001\,532} \cdot 10^6 + {\color{Brown}664\,392}.</math>

Die benötigten Produkte sind
:<math>P_1 = X_h \cdot Y_h = {\color{Blue}084\,232} \cdot {\color{Red}001\,532} = 000\,129\,043\,424</math>,
:<math>P_2 = X_l \cdot Y_l = {\color{OliveGreen}332\,233} \cdot {\color{Brown}664\,392} = 220\,732\,947\,336</math> und
:<math>P_3 = </math><!-- damit diese Zeile in der SVG Ansicht genauso eingerückt wird, Ursache des Bugs und Funktionsweise der Lösung unklar --><math>\!(X_h + X_l) \cdot (Y_h + Y_l) = ({\color{Blue}084\,232} + {\color{OliveGreen}332\,233}) \cdot ({\color{Red}001\,532} + {\color{Brown}664\,392}) = 416\,465\ \cdot\ 665\,924 = 277\,334\,038\,660.
</math>

Der Algorithmus würde die Produkte <math>P_1</math>, <math>P_2</math> und <math>P_3</math> rekursiv bestimmen. Es bleibt das Ergebnis gemäß obiger Formel zusammenzusetzen:
:<math>
\begin{array}{rll}
X \cdot Y & = & P_1 \cdot 10^{12} + \big(P_3 - (P_1 + P_2)\big) \cdot 10^6 + P_2 \\
     & = & 000\,129\,043\,424 \cdot 10^{12} \\
     &   & + \big(277\,334\,038\,660 - (000\,129\,043\,424 + 220\,732\,947\,336)\big)\cdot 10^6 \\
     &   & + 220\,732\,947\,336.
\end{array}
</math>

Während die Schulmethode 110 Ziffernmultiplikationen und 90 Additionen (ohne Überträge) benötigt, sind es hier 92 Multiplikationen und 83 Additionen.

== Verallgemeinerung ==

Statt in zwei Teile, können die zu multiplizierenden Zahlen auch in mehr Teile zerlegt werden. Durch geschickte [[Linearkombination]] von Teilergebnissen genügen dann bei Zerlegung in <math>d+1</math> Teile <math>2d+1</math> Multiplikationen auf den kleineren Zahlen. Rekursiv angewandt führt dieses Verfahren dann zum [[Toom-Cook-Algorithmus]].

== Literatur ==

* A. Karatsuba, Y. Ofman: ''Multiplication of Many-Digital Numbers by Automatic Computers.'' In: ''Soviet Physics-Doklady.'' 7, 1963, S. 595–596 (engl. Übersetzung des russ. Originals. In: ''Doklady Akad. Nauk SSSR.'' Band 145, 1962, S. 293–294).
* A. A. Karacuba: ''Berechnungen und die Kompliziertheit von Beziehungen.'' In: ''Elektron. Informationsverarb. Kybernetik.'' 11, 1975, S. 603–606.
* A. A. Karatsuba: ''The Complexity of Computations.'' In: ''Proc. Steklov Inst. Math.'' 211, 1995, S. 169–183 ([http://www.cs.ru/personal/karatsuba/divcen.pdf cs.ru] PDF; engl. Übersetzung des russ. Originals. In: ''Trudy Mat. Inst. Steklova.'' 211, 1995, S. 186–202).
* D. E. Knuth: ''The Art of Computer Programming.'' Band 2: ''Seminumerical Algorithms.'' Addison-Wesley Publ.Co., Reading, Mass., 1969, ISBN 0-201-89684-2.

== Weblinks ==

* [https://mathworld.wolfram.com/KaratsubaMultiplication.html ''Karatsuba Multiplication.''] auf MathWorld
* D. J. Bernstein: [https://cr.yp.to/papers/m3.pdf ''Multidigit multiplication for mathematicians.''] (PDF; 276&nbsp;kB). Mathematische Darstellung diverser Multiplikationsalgorithmen. Behandelt auch den Karazuba-Algorithmus.
* [http://www.ccas.ru/personal/karatsuba/divcen.htm ''Karatsuba Multiplication on Fast Algorithms and the FEE.'']

== Einzelnachweise und Anmerkungen ==
<references />

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