Karazuba-Algorithmus

Der Karatsuba-Algorithmus ist ein effizienter 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 (bzw. der russischen Bauernmultiplikation im Binärsystem), der Laufzeitkomplexität $O(n^{2})$ besitzt, aber für hinreichend große Zahlen auch langsamer als der Schönhage-Strassen-Algorithmus, dessen Laufzeitkomplexität $O(n\cdot \log(n)\cdot \log(\log(n)))$ 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 Prinzip Teile und herrsche und ist ein Spezialfall des Toom-Cook-Algorithmus.

Idee des Algorithmus

Zunächst werden die beiden zu multiplizierenden Zahlen in zwei Teile aufgespalten. Nach dem Distributivgesetz ergeben sich dann insgesammt vier Summanden, die durch vier Multiplikationen zusammen mit einigen Shift-Operationen berechnet werden können. Statt nun vier Multiplikationen durchzuführen kann mit Hilfe zweier Summanden die Summe der beiden anderen Summanden indirekt berechnet werden, wobei nun eine Multiplikation genügt. Führt man diese Verfahren rekuriv durch, so erhält man eine wesentlich günstigere Laufzeit, als nach der naiven Schulmethode.

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.

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 ein eine andere, schneller berechenbare Form zu bringen. Ausmultiplizieren ergibt zunächst