Karatsuba-Algorithmus

Der Karatsuba-Algorithmus ist ein Algorithmus zur Multiplikation zweier ganzer Zahlen, der nach dem rekursiven Teilen-und-Herrschen-Prinzip arbeitet. Er wurde 1960 von Anatoli Alexejewitsch Karazuba (engl. Karatsuba, russisch Анато́лий Алексе́евич Карацу́ба) entwickelt und 1962 veröffentlicht. Mit einer Laufzeitkomplexität von $O(n^{\log_2(3)}) = O(n^{1{,}585})$ ist er deutlich schneller als der naive Algorithmus nach der Schulmethode. Dieser (und auch dessen implizite Übertragung auf das Binärsystem in Form der russischen Bauernmultiplikation) besitzt eine Laufzeitkomplexität von $O(n^2)$. Für hinreichend große Zahlen ist der Karatsuba-Algorithmus aber auch langsamer als seine Verallgemeinerungen, wie der Toom-Cook-Algorithmus oder der Schönhage-Strassen-Algorithmus (1971), 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 bis 2007 als schnellster Algorithmus zur Multiplikation ganzer Zahlen galt.

Idee des Algorithmus

Multiplizieren verursacht in der Schulmethode quadratischen Aufwand, während Additionen und Verschiebeoperation nur linearen Aufwand haben. Die Idee ist, nach dem „Teile und herrsche“-Prinzip die beiden zu multiplizierenden Zahlen in zwei Teile aufzuspalten, und die teuren Multiplikationen (so gut es geht) durch Additionen und Verschiebeoperationen zu ersetzen. Das Ausmultiplizieren der geteilten 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 kann aber auch als Summe geschrieben werden, die aus einem (neuen) Produkt und den anderen beiden Teiltermen besteht. Insgesamt spart man so also eine teure Teil-Multiplikation ein. Führt man dieses Verfahren rekursiv durch, so erhält man eine wesentlich günstigere Laufzeit als nach der naiven Schulmethode.

Der Algorithmus im Detail

Der hier angegebene Algorithmus gilt für natürliche Zahlen, er lässt sich aber leicht auch auf ganze Zahlen verallgemeinern, indem ihre Vorzeichen gesondert berücksichtigt werden. Die Faktoren $x$ und $y$ seien dargestellt im Stellenwertsystem zur Basis $b$; der Wert von $b$ ist unerheblich - die Beispiele weiter unten verwenden Dezimalzahlen. Die Längen beider Ziffernfolgen seien gerade und gleich $2n$. Das ist immer erreichbar durch geeignet vorangestellte Nullen; an der Laufzeitabschätzung unten ändert es nichts.

Die Ziffernfolgen seien also

$x = x_{2n-1} \ldots x_0$ und

$y = y_{2n-1} \ldots y_0.$

Jede Ziffernfolge wird nun in zwei Folgen der Länge n aufgespalten. Das liefert die vier Zahlen

$x_h = x_{2n-1} \ldots x_n$ und $x_l = x_{n-1} \ldots x_0$ sowie

$y_h = y_{2n-1} \ldots y_n$ und $y_l = y_{n-1} \ldots y_0.$

Damit ist

$x = x_h \cdot b^n + x_l$ und

$y = y_h \cdot b^n + y_l.$

Ausmultipliziert ergibt sich

$x \cdot y = (x_h \cdot b^n + x_l) \cdot (y_h \cdot b^n + y_l) = x_h y_h \cdot b^{2n} + (x_h y_l + x_l y_h) \cdot b^n + x_l y_l.$

Den Term $(x_h y_l + x_l y_h)$ kann man nun in eine andere, hier schneller berechenbare Form bringen:

$x_h y_l + x_l y_h = (x_h + x_l) \cdot (y_h + y_l) - x_h y_h - x_l y_l.$

Damit ergibt sich für das Produkt die Darstellung

$x \cdot y = x_h y_h \cdot b^{2n} + ((x_h + x_l) \cdot (y_h + y_l) - x_h y_h - x_l y_l) \cdot b^n + x_l y_l,$

in der nur noch die drei "kurzen" Produkte

$P_1 = x_h \cdot y_h$

$P_2 = x_l \cdot y_l$

$P_3 = (x_h + x_l) \cdot (y_h + y_l)$

erscheinen. Rekursiv berechnet und mit einfachen Verschiebe- und Additionsoperationen verknüpft ergeben sie

$x \cdot y = P_1 \cdot b^{2n} + (P_3 - P_1 - P_2) \cdot b^n + P_2.$

Laufzeitanalyse

Eine Multiplikation zweier $n$-stelliger Zahlen wird zurückgeführt auf drei Multiplikationen von je zwei $n/2$ bzw. $n/2+1$-stelligen Zahlen sowie vier Additionen bzw. Subtraktionen $n$-stelliger Zahlen. Die für letzteres benötigte Zeit ist O(n). Wenn $T(n)$ die Laufzeit bezeichnet, die zur Multiplikation zweier $n$-stelliger Zahlen nötig ist, so gilt:

$T(n) = 3T(n/2+1) + O(n)$

Mit den Bezeichnungen des hier anwendbaren Master-Theorems ist $a=3$, $b=2$ und c=1, also $\log_b a = \log_2 3 \leq 1{,}585$. Der lineare Faktor für die Additionen bzw. Subtraktionen wird also von dem rekursiven Aufwand für die Multiplikationen dominiert (mathematisch ausgedrückt $n \in O (n^{\log_2 3})$). Damit gilt:

$T(n) \in O (n^{\log_2 3}) = O(n^{1{,}585})$

Beispiel

Gegeben seien die Zahlen

$x = 84\ 232\ 332\ 233$ und

$y = 1\ 532\ 664\ 392.$

Mit vorangestellten Nullen auf gerade und gleiche Länge aufgefüllt ergeben sich die Ziffernfolgen

$x = 084\ 232\ 332\ 233$ und

$y = 001\ 532\ 664\ 392$

der Länge $2n = 12$, die zerlegt werden in vier Folgen der Länge $n = 6:$

$x_h = 084\ 232$ und $x_l = 332\ 233$ sowie

$y_h = 001\ 532$ und $y_l = 664\ 392.$

Es gilt

$x = x_h \cdot 10^6 + x_l = 084\ 232 \cdot 10^6 + 332\ 233$ und

$y = y_h \cdot 10^6 + y_l = 001\ 532 \cdot 10^6 + 664\ 392.$

Die benötigten Produkte sind

$P_1 = x_h y_h = 084\ 232 \cdot 001\ 532 = 000\ 129\ 043\ 424,$

$P_2 = x_l y_l = 332\ 233 \cdot 664\ 392 = 220\ 732\ 947\ 336$ und

$P_3 = (x_h + x_l) \cdot (y_h + y_l) = (084\ 232 + 332\ 233) \cdot (001\ 532 + 664\ 392) = 416\ 465 \cdot 665\ 924 = 277\ 334\ 038\ 660.$

Der Algorithmus würde die Produkte $P_1$, $P_2$ und $P_3$ rekursiv bestimmen. Es bleibt das Ergebnis gemäß obiger Formel zusammenzusetzen:

$\begin{matrix} x \cdot y & = & P_1 \cdot 10^{12} + (P_3 - P_1 - P_2) \cdot 10^6 + P_2 \\ & = & 000\ 129\ 043\ 424 \cdot 10^{12} \\ & & + (277\ 334\ 038\ 660 - 000\ 129\ 043\ 424 - 220\ 732\ 947\ 336) \cdot 10^6 \\ & & + 220\ 732\ 947\ 336 \end{matrix}$

Implementierung in Java

Eine Implementierung in Java kann wie folgt aussehen:

public static BigInteger karatsuba (BigInteger x, BigInteger y)
{
        // Verwende Standard Multiplikation bei kleinen Eingaben
        int n = Math.max (x.bitLength(), y.bitLength());
        if (n <= 1500) return x.multiply (y);
 
        // teile; x = xH * b^n + xL ,   y = yH * b^n + yL
        n = n / 2;
        BigInteger xH = x.shiftRight (n);
        BigInteger xL = x.subtract   (xH.shiftLeft(n));
        BigInteger yH = y.shiftRight (n);
        BigInteger yL = y.subtract   (yH.shiftLeft(n));
 
        // berechne die Teilresultate
        BigInteger p1 = karatsuba (xH, yH);
        BigInteger p2 = karatsuba (xL, yL);
        BigInteger p3 = karatsuba (xL.add (xH), yL.add (yH));
 
        // Setze die Teile zum Gesamtergebnis zusammen
        return p1.shiftLeft (2*n).add (p3.subtract (p1).subtract (p2).shiftLeft (n)).add (p2);
}

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 $d+1$ Teile $2d+1$ Multiplikationen auf den kleineren Zahlen. Rekursiv angewandt führt dieses Verfahren dann zum Toom-Cook-Algorithmus.

Literatur

• A. Karatsuba and Yu Ofman: Multiplication of Many-Digital Numbers by Automatic Computers. Doklady Akad. Nauk SSSR, Vol. 145 (1962), pp. 293–294. Translation in Physics-Doklady, 7 (1963), pp. 595–596.
• Karacuba A.A. Berechnungen und die Kompliziertheit von Beziehungen. Elektron. Informationsverarb. Kybernetik, 11, 603–606 (1975).
• Karatsuba A.A. The complexity of computations. Proc. Steklov Inst. Math., 211, 169–183 (1995); translation from Trudy Mat. Inst. Steklova, 211, 186–202 (1995).
• Knuth D. E. The art of computer programming. v.2. Addison-Wesley Publ.Co., 724 pp., Reading (1969).

Weblinks

• Schnelle Multiplikation beim Algorithmus der Woche
• Karatsuba Multiplication on MathWorld
• Bernstein, D. J.: Multidigit multiplication for mathematicians (PDF; 276 kB). Mathematische Darstellung diverser Multiplikations Algorithmen. Behandelt auch den Karatsuba Algorithmus.

• Karatsuba Multiplication on Fast Algorithms and the FEE