Arithmetik

Die Schulmethode der Multi­plikation von zwei m-Bit-Zahlen a und b ist zwar die einfachste, aber nicht die effizienteste Methode. Die Zeit­komplexität der Schulmethode beträgt Θ(m²). Dies liegt daran, dass eine parallelo­gramm­förmige Tabelle mit m Zeilen der Länge m erzeugt wird. Jedes Bit des Operanden a wird mit jedem Bit des Operanden b multipliziert und anschließend werden die m² Zwischen­ergebnisse addiert.

Bild 1: Schulmethode der Multiplikation  9·11 = 99

Divide-and-Conquer-Ansatz

Es liegt nahe, zu versuchen, die Berechnung mittels der Divide-and-Conquer-Strategie zu beschleunigen. Die beiden m-Bit-Zahlen a und b werden jeweils in der Mitte aufgeteilt, also dargestellt als a = a₁·2^k + a₀ und b = b₁·2^k + b₀. Hierbei ist k = m div 2. Das Teilstück a₁ enthält die m-k höher­wertigen Bits und das Teilstück a₀ die k nieder­wertigen Bits von a (Bild 2). Ent­sprechendes gilt für b.

Das Produkt c = a · b ergibt sich dann als

c  =  a₁·b₁ ·2^2k + (a₀·b₁ + a₁·b₀)·2^k + a₀·b₀

Die einzelnen Teilprodukte lassen sich schneller berechnen, da die Operanden nur die halbe Länge haben, nämlich in Zeit Θ((m/2)²) = Θ(m²/4), also in einem Viertel der Zeit der ursprüng­lichen Berechnung. Da aber vier dieser Teilprodukte zu berechnen sind, ist leider nichts gewonnen.

Der Trick des Karatsuba-Algorithmus (nach A. Karatsuba) besteht darin, die obige Formel so umzuformen, dass sie nur noch aus drei Teil­produkten besteht.

Idee

Die Formel für die Berechnung des Produkts c wird folgender­maßen umgeformt:

c   =   a₁·b₁ ·2^2k + (a₀·b₁ + a₁·b₀)·2^k + a₀·b₀

     =   a₁·b₁ ·2^2k + ((a₁ + a₀) · (b₁ + b₀) – a₁·b₁ – a₀·b₀)·2^k + a₀·b₀

In der zweiten Zeile sind nur noch drei Multi­plikationen erforderlich:

Die Teilprodukte a₁·b₁ und a₀·b₀ werden nur einmal ausgerechnet und dann in der Formel mehrfach verwendet. Dafür sind eine Addition und zwei Subtraktionen hinzu­gekommen, aber diese erfordern nur höchstens linearen Aufwand und sind damit auch zusammen­genommen deutlich schneller als eine Multi­plikation.

Umsetzung

Die Aussage, dass eine Addition und zwei Subtraktionen schneller als eine Multi­plikation sind, stimmt natürlich erst ab einer Operanden­länge von k  >  3.

Es bietet sich an, den Karatsuba-Algorithmus rekursiv zu implementieren, d.h. die drei Teilprodukte ebenfalls mit dem Karatsuba-Algorithmus zu multiplizieren. Aber spätestens ab einer Länge von  ≤  3 werden die Operanden dann nicht mehr weiter rekursiv behandelt, sondern direkt nach der Schulmethode miteinander multipliziert.

In der Praxis wird bei der Multi­plikation von Langzahlen die Rekursion dann beendet, wenn die Operanden mit dem normalen Multi­plikationsbefehl des Computers multipliziert werden können.

Programm

Das folgende Python-Programm ver­anschaulicht die Multi­plikation von zwei großen ganzen Zahlen mit dem Karatsuba-Algorithmus. Die höher­wertigen Teilstücke von a und b werden durch Rechts­schieben um k Bit erzeugt; die nieder­wertigen Teilstücke werden durch Maskieren mit k Einsen erzeugt. Die mehrfach verwendeten Produkte a₁·b₁ und a₀·b₀ werden in Variablen p2 und p0 gespeichert. Die Rekursion wird hier bei einer Operanden­länge von 16 Bit beendet.

Die anfängliche Abfrage, ob einer der Operanden gleich 0 ist, vermeidet unnötige rekursive Aufrufe in Fällen, wenn die Längen der Operanden a und b sich stark unter­scheiden; dann nämlich ist a₁ bzw. b₁ in den rekursiven Aufrufen häufig gleich 0. Für die Korrektheit erforderlich ist die Abfrage nicht.

Zeitkomplexität

Das Programm enthält eine Anzahl von Operationen der Komplexität O(k), wie etwa Schiebe­operationen, Additionen und Subtraktionen von k-Bit-Operanden. Darüber hinaus enthält es drei rekursive Aufrufe mit Operanden der Länge k.

Mit k = m/2 gilt damit

T(m)  =  3·T(m/2) + c·m/2

Die Auf­lösung dieser Rekurrenz ergibt

T(m)  ∈  O(3^{log m})

Verblüffenderweise gilt

3^{log m}  =  m^{log 3}

Denn mit den Logarithmen-Formeln x = 2^{log x} und (2^x)^y = 2^x·y gilt

3^{log m}  =  (2^{log 3})^{log m}  =  2^{log 3 · log m}  =  2^{log m · log 3}  =  (2^{log m})^{log 3}  =  m^{log 3}

Da log(3)  1,585, ist die Karatsuba-Multi­plikation mit der Komplexität O(m^1,585) wesentlich schneller als die Schulmethode mit der Komplexität Θ(m²).

Literatur

[Knu 01]   D.E. Knuth: Arithmetik. Springer (2001)

[DMS 14]   M. Dietzfelbinger, K. Mehlhorn, P. Sanders: Algorithmen und Datenstrukturen. Springer Vieweg (2014)