Karazuba-Algorithmus
Der Karatsuba-Algorithmus ist ein Algorithmus zur Multiplikation zweier ganzer Zahlen. Mit einer Laufzeitkomplexität von 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 . Für hinreichend große Zahlen ist er aber auch langsamer als der Schönhage-Strassen-Algorithmus, dessen Laufzeitkomplexität 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 der einfachste und asymptotisch langsamste Spezialfall des Toom-Cook-Algorithmus (siehe unten).
Idee des Algorithmus
Zunächst werden die beiden zu multiplizierenden Zahlen in zwei Teile aufgespalten. Ausmultiplizieren ergibt dann insgesamt vier Summanden, die durch vier Multiplikationen gebildet werden und anschließend durch Verschiebe- und Additionsoperationen zusammengesetzt werden können. Statt nun vier Multiplikationen durchzuführen kann mit Hilfe zweier Summanden die Summe der beiden anderen Summanden indirekt berechnet werden, wobei dabei eine Multiplikation genügt. 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
- und
Der Algorithmus teilt diese Ziffern nun in
- und sowie
- und
auf, so dass sich diese auch Darstellen lassen mit
- und
- ,
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
Genauso erhält man auch
- .
In vorangegangene Gleichung eingesetzt ergibt sich nun
- .
Man erkennt, dass im Wesentlichen nur noch die drei Produkte
- ,
- und
rekursiv berechnet und - mittels einfachen Verschiebe- und Additionsoperationen - verknüpft werden müssen zu
- .
Beispiel
Wir betrachten als Beispiel die Zahlen
- und
Gemäß obiger Erläuterung stellen wir diesen Zahlen noch ausreichend Nullen voran, das heißt wir setzen
- und
Wir haben nun zwei natürliche Zahlen der Länge 12, das heißt es ist . Diese beiden Zahlen können wir nun zerlegen in
- und sowie
- und
Es gilt
- und
Wir bilden nun zunächst die Produkte
- und
Zuletzt bestimmen wir noch
Der Algorithmus würde die Produkte und rekursiv bestimmen. Es bleibt das Ergebnis gemäß obiger Formel zusammenzusetzen:
Laufzeitabschätzung
comming soon
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.