Karatsuba-Algorithmus

Karatsuba-Algorithmus

Der Karatsuba-Algorithmus (1960) ist ein Algorithmus zur Multiplikation zweier ganzer Zahlen. 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 Laufzeitkomplexität O(n2). 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. Der Algorithmus von Anatoli Alexejewitsch Karazuba (engl. Karatsuba, russisch Анато́лий Алексе́евич Карацу́ба) arbeitet nach dem rekursiven Prinzip Teile und herrsche und hat viele Verallgemeinerungen. Eine solche Verallgemeinerung der Methode von Karatsuba ist der Toom-Cook-Algorithmus (siehe unten).

Inhaltsverzeichnis

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 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)

Wir können das Master-Theorem anwenden. Mit den Bezeichnungen von dort haben wir 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

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 P1, P2 und P3 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


Wikimedia Foundation.

Игры ⚽ Нужен реферат?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Schönhage-Strassen-Algorithmus — Der Schönhage Strassen Algorithmus ist ein Algorithmus zur Multiplikation zweier n stelliger ganzer Zahlen. Er wurde 1971 von Arnold Schönhage und Volker Strassen entwickelt.[1] Der Algorithmus basiert auf einer „superschnellen“ Variante der… …   Deutsch Wikipedia

  • Toom-Cook-Algorithmus — 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… …   Deutsch Wikipedia

  • Schönhage-Strassen — Der Schönhage Strassen Algorithmus ist ein Algorithmus zur Multiplikation zweier n stelliger ganzer Zahlen. Er wurde 1971 von Arnold Schönhage und Volker Strassen entwickelt.[1] Der Algorithmus basiert auf einer „superschnellen“ Variante der… …   Deutsch Wikipedia

  • Computer-Algebra — Die Computeralgebra ist das Teilgebiet der Mathematik, das sich mit der symbolischen Manipulation algebraischer Ausdrücke beschäftigt. Inhaltsverzeichnis 1 Zweck 2 Effiziente exakte Arithmetik mit ganzen Zahlen 3 Effiziente exakte Arithmetik mit… …   Deutsch Wikipedia

  • Computeralgebra — Die Computeralgebra ist das Teilgebiet der Mathematik und Informatik, das sich mit der automatisierten, symbolischen Manipulation algebraischer Ausdrücke beschäftigt. Inhaltsverzeichnis 1 Überblick 2 Zugrundeliegende Strukturen 2.1 Gruppen …   Deutsch Wikipedia

  • Faktor (Mathematik) — Die Multiplikation (v. lat.: multiplicare = vervielfachen, auch Malnehmen genannt) ist eine der vier Grundrechenarten in der Arithmetik. Inhaltsverzeichnis 1 Namensgebung 2 Rechengesetze 2.1 Gaußsche Summenfaktor Regel 3 …   Deutsch Wikipedia

  • Fingermultiplikation — Die Multiplikation (v. lat.: multiplicare = vervielfachen, auch Malnehmen genannt) ist eine der vier Grundrechenarten in der Arithmetik. Inhaltsverzeichnis 1 Namensgebung 2 Rechengesetze 2.1 Gaußsche Summenfaktor Regel 3 …   Deutsch Wikipedia

  • Malnehmen — Die Multiplikation (v. lat.: multiplicare = vervielfachen, auch Malnehmen genannt) ist eine der vier Grundrechenarten in der Arithmetik. Inhaltsverzeichnis 1 Namensgebung 2 Rechengesetze 2.1 Gaußsche Summenfaktor Regel 3 …   Deutsch Wikipedia

  • Multiplikand — Die Multiplikation (v. lat.: multiplicare = vervielfachen, auch Malnehmen genannt) ist eine der vier Grundrechenarten in der Arithmetik. Inhaltsverzeichnis 1 Namensgebung 2 Rechengesetze 2.1 Gaußsche Summenfaktor Regel 3 …   Deutsch Wikipedia

  • Multiplizieren — Die Multiplikation (v. lat.: multiplicare = vervielfachen, auch Malnehmen genannt) ist eine der vier Grundrechenarten in der Arithmetik. Inhaltsverzeichnis 1 Namensgebung 2 Rechengesetze 2.1 Gaußsche Summenfaktor Regel 3 …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”