Karazuba-Algorithmus

Der Karatsuba-Algorithmus ist ein Algorithmus zur Multiplikation zweier ganzer Zahlen. Mit einer Laufzeitkomplexität von $O(n^{\log _{2}(3)})\approx O(n^{1,58496})$ ist er deutlich schneller als der naive Algorithmus nach der Schulmethode. Dieser (und auch deren implizite Übertragung auf das Binärsystem in Form der russischen Bauernmultiplikation) besitzt Laufzeitkomplexität $O(n^{2})$. 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 bekannter Algorithmus zur Multiplikation ganzer Zahlen gilt. Der Algorithmus von Karatsuba arbeitet nach dem rekursiven Prinzip Teile und herrsche und ist der einfachste und asymptotisch langsamste Spezialfall des Toom-Cook-Algorithmus (siehe unten).

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

Wir gehen von zwei natürlichen Zahlen x und y aus, deren Länge jeweils 2n beträgt. Der Algorithmus kann in einfacher Weise so verallgemeinert werden, dass er auch auf ganzen Zahlen funktioniert, indem Vorzeichen gesondert berücksichtigt werden. Zahlen mit ungerader Länge können als solche mit gerader Länge dargestellt werden, indem eine führende Null vorangestellt wird. Bei Zahlen ungleicher Länge kann die kleinere Zahl ebenfalls durch voranstellen von Nullen auf gleiche Länge aufgefüllt werden. An der Laufzeitabschätzung unten ändert dies nichts. Ebenfalls unerheblich ist das betrachtete Stellenwertsystem. Wir werden in Beispielen mit Dezimalzahlen operieren.

Seien x und y dargestellt durch die Ziffernfolgen

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

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

Der Algorithmus teilt diese Ziffern nun in

$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}$

auf, so dass sich diese auch Darstellen lassen mit

$x=x_{h}\cdot b^{n}+x_{l}$ und

$y=y_{h}\cdot b^{n}+y_{l}$,

wobei b die Basis des verwendeten Stellenwertsystems ist.

Im Folgenden werden wir nun versuchen die Multiplikation von x und y in eine andere, schneller berechenbare Form zu bringen. Ausmultiplizieren ergibt zunächst

$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}.$

Genauso erhält man auch

$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}$.

In vorangegangene Gleichung eingesetzt ergibt sich nun

$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}$.

Man erkennt, dass im Wesentlichen nur noch die drei 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})$

rekursiv berechnet und - mittels einfachen Verschiebe- und Additionsoperationen - verknüpft werden müssen zu

$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$-stelligen Zahlen sowie vier Additionen bzw. Subtraktionen $n$-stelliger Zahlen. Die für letzteres benötigte Zeit ist $O(n)$. Damit ergibt sich als Rekursionsgleichung für die Laufzeit $T(n)$, die zur Multiplikation zweier $n$-stelligen Zahlen nötig ist,

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

Wir bestimmen das asymptotische Verhalten dieser Funktion mit Hilfe des Master-Theorems. Mit den Bezeichnungen von dort haben wir $a=3$ und $b=2$, also $\log _{b}a=\log _{2}3\approx 1,585$. Daher müssen wir $O(n)$ mit $O(n^{1,585})$ vergleichen. Wir stellen fest, dass $O(n)$ "echt kleiner" ist (genauer: für jede Funktion $f\in O(n)$ finden wir ein $\epsilon >0$, so dass $f\in O(n^{\log _{2}3-\epsilon })$). Also befinden wir uns im ersten Fall des Master-Theorems und können schließen, dass

$T(n)\in \Theta (n^{\log _{2}3})\approx \Theta (n^{1.585})$

ist.

Beispiel

Wir betrachten als Beispiel die Zahlen

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

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

Gemäß obiger Erläuterung stellen wir diesen Zahlen noch ausreichend Nullen voran, das heißt wir setzen

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

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

Wir haben nun zwei natürliche Zahlen der Länge 12, das heißt es ist $n=6$. Diese beiden Zahlen können wir nun zerlegen in

$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.$

Wir bilden nun zunächst die Produkte

$P_{1}=x_{h}y_{h}=084\ 232\cdot 001\ 532=000\ 129\ 043\ 424$ und

$P_{2}=x_{l}y_{l}=332\ 233\cdot 664\ 392=220\ 732\ 947\ 336.$

Zuletzt bestimmen wir noch

$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 nicht auf Effizienz ausgelegete Implementierung in Java kann wie folgt aussehen:

public static BigInteger karatsuba (BigInteger x, BigInteger y)
{
       int n = Math.max (x.bitLength(), y.bitLength());

       // Verwende Standard Multiplikation bei kleinen Eingaben
       if (n <= 1500) return x.multiply (y);

       n = n / 2;

       // teile; x = xH b^n + xL ,   y = xH b^n + yL
       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));

       // Setzte 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 angewand führt dieses Verfahren dann zum Toom-Cook-Algorithmus.

Weblinks

• Schnelle Multiplikation beim Algorithmus der Woche
• 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.
• Karatsuba Multiplication on MathWorld
• Bernstein, D. J., "Multidigit multiplication for mathematicians". Mathematische Darstellung diverser Multiplikations Algorithmen. Behandelt auch den Karatsuba Algorithmus.