Arithmetik

Karatsuba-Multiplikation

 aufwärts

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 Θ(m2). 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 multi­pliziert und anschließend werden die m2 Zwischen­ergebnisse addiert.

  1001·1011
  1001
+  0000
+   1001
+    1001
= 1100011
Bild 1: Schulmethode der Multiplikation  9·11 = 99

Divide-and-Conquer-Ansatz

Es liegt nahe, zu versuchen, die Berechnung mittels der Divide-and-Conquer-StrategieErklärung zu beschleunigen. Die beiden m-Bit-Zahlen a und b werden jeweils in der Mitte aufgeteilt, also dargestellt als a = a1·2k + a0 und b = b1·2k + b0. Hierbei ist k = m div 2 und a1 ist der Teil mit den m-k höher­wertigen Bits und a0 der Teil mit den k nieder­wertigen Bits von a. Ent­sprechendes gilt für b.

Das Produkt c = a · b ergibt sich dann als

c  =  a1·b1 ·22k + (a0·b1 + a1·b0)·2k + a0·b0

Die einzelnen Teilprodukte lassen sich schneller berechnen, da die Operanden nur die halbe Länge haben, nämlich in Zeit Θ((m/2)2) = Θ(m2/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. Karatsubazur Person) 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   =   a1·b1 ·22k + (a0·b1 + a1·b0)·2k + a0·b0

     =   a1·b1 ·22k + ((a1 + a0) · (b1 + b0) – a1·b1 – a0·b0)·2k + a0·b0

In der zweiten Zeile sind nur noch drei Multi­plikationen erforderlich; die Teilprodukte a1·b1 und a0·b0 werden nur einmal ausgerechnet und dann 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 multi­plizieren. Aber spätestens ab einer Länge von kleiner gleich 3 werden die Operanden dann nicht mehr weiter rekursiv behandelt, sondern direkt nach der Schulmethode miteinander multi­pliziert.

In der Praxis wird bei der Multi­plikation von Langzahlen die Rekursion dann beendet, wenn die Operanden mit dem normalen Multi­plikationsbefehl des Computers multi­pliziert 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 a1·b1 und a0·b0 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 a1 bzw. b1 in den rekursiven Aufrufen häufig gleich 0. Für die Korrektheit erforderlich ist die Abfrage nicht.

 

def karatsuba_mul(a, b):
    if a==0 or b==0:
        return 0
    m=max(a.bit_length(), b.bit_length())
    if m<=16:
        return a*b
    else:
        k=m//2
        a1=a>>k
        a0=a & (1<<k)-1  
        b1=b>>k
        b0=b & (1<<k)-1
        p2=karatsuba_mul(a1, b1)
        p1=karatsuba_mul(a1+a0, b1+b0)
        p0=karatsuba_mul(a0, b0)
        c2=p2 << 2*k
        c1=p1-p2-p0 << k
        return c2+c1+p0

# Test
if __name__=="__main__":
    a=123456789012345678901234567890
    b=987654321098765432109876543210
    print a, b
    print a*b
    print karatsuba_mul(a, b)

 

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 Auflösung dieser Rekurrenz ergibt

T(m)  Element  O(mlog 3)

Da log(3) ungefähr gleich 1,585, ist die Karatsuba-Multi­plikation mit der Komplexität O(m1,585) wesentlich schneller als die Schulmethode mit der Komplexität Θ(m2).

 

Literatur

[Knu 01]D.E. Knuth: Arithmetik. Springer (2001)
[DMS 14]M. Dietzfelbinger, K. Mehlhorn, P. Sanders: Algorithmen und Datenstrukturen. Springer Vieweg (2014)

 

up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 11.09.2018   Updated: 15.09.2018
Valid HTML 4.01 Transitional