Karatsuba Algorithmus mit Excel VBA
06.02.2009
Aktualisierung am 30.01.2011: Mittlerweile ist das Add-In in der ersten Version erschienen; hier der Link zur aktuellen Version des Add-Ins: In Excel mit sehr großen Zahlen rechnen – Teil 5 – Add-In für Excel.Aktualisierung am 09.11.2010: Vor einiger Zeit gab es im Forum „Office-Lösung“ eine weitere sehr interessante Diskussion, wie in Excel der Wert von 80 ^ 200 ausgerechnet werden könnte. Hierzu konnte dann Karatsuba effektiv eingesetzt werden, allerdings nur mit ein paar Code-Anpassungen. Deshalb entsteht zur Zeit eine neue Version der Anwendung. Eine Artikelserie habe ich gestern dazu in meinem weiteren Blog gestartet; hier der Link zum ersten Teil der Serie: In Excel mit sehr großen Zahlen rechnen.
Weitere Artikel zum Subtrahieren, Multiplizieren oder Potenzieren folgen.
In meinem Lieblingsforum Office-Lösung hatte vor kurzem jemand folgende Idee: "Multiplizieren wir, ausgehend von der Zahl 2, das Ergebnis immer mit sich selbst".
Nun, wer es mal mit Excel Formeln versucht, wird schnell feststellen, dass Excel ab einer bestimmten Größe ein Teil des Ergebnisses einfach abschneidet. Stellt sich die Frage, schafft es vielleicht VBA? Hmm, teilweise. Auch dort ist bedingt durch den darstellbaren Bereich der eingebauten Datentypen irgendwann Schluss. Zudem stellt sich das Problem der benötigten Rechenzeit.
Wenn man im Internet nach 'Multiplikation großer Ganzzahlen' sucht, findet man relativ schnell Informationen zu einigen Verfahren, die Multiplikationen durch Additionen ersetzen. Ein Verfahren ist der 'Karatsuba-Algorithmus'. Dieser ist zwar nicht neu, reduziert jedoch erheblich die Anzahl an benötigten Multiplikationen.
Und wie funktioniert der Algorithmus? Nun, die Grundidee ist, einerseits Multiplikationen durch Additionen und Verschiebeoperationen zu ersetzen und andererseits durch Aufteilung der zu multiplizierenden Zahlen Rechenschritte einzusparen. Die aufgeteilten Zahlen werden miteinander multipliziert und später wieder zusammengesetzt. Das Prinzip nennt sich 'Teil und Herrsche Prinzip', in Englisch 'divide and conquer'. Das Verfahren kann prima rekursiv angewandt werden, denn auch die Teilzahlen lassen sich wiederum aufteilen.
Beispiel für den Algorithmus
Lassen wir mal die mathematischen Beweise ausser Betracht und stellen uns vor, wir möchten die Zahlen 123456789 und 98765 miteinander multiplizieren. Als Ergebnis müssten wir 12193258259412 erhalten. Zunächst stellen wir fest, dass die beiden Ausgangszahlen sind unterschiedlich lang sind (9 Ziffern und 5 Ziffern). Wir stellen den Zahlen einfach ein paar Nullen voran und erhalten somit:
Zahl_1 = 0123456789 Zahl_2 = 0000098765Wie sicherlich bemerkt, habe ich auch Zahl_1 eine Null vorangestellt und zwar aus dem Grunde, dass beide Zahlen nun 10 Stellen haben. 10 geteilt durch 2 ergibt 5 Stellen. Damit erhalten wir nach Aufteilung folgende vier Zahlen:
Zahl_1_1 = 01234 und Zahl_1_1 = 56789 Zahl_2_1 = 00000 und Zahl_2_2 = 98765Unsere Zahlen können gemäß folgender Rechenmethode wieder zusammengesetzt werden, wenn für N gleich der halben Stellenanzahl unserer Ausgangszahlen ist:
Zahl_1 = Zahl_1_1 * 10 hoch N + Zahl_1_2 Zahl_2 = Zahl_2_1 * 10 hoch N + Zahl_2_2In unserem Beispiel also:
Zahl_1 = 01234 * 10^5 + 56789 = 0123456789 Zahl_2 = 00000 * 10^5 + 98765 = 0000098765Der Algorithmus stützt sich zunächst auf die Bildung dreier Teilprodukte, die folgender Regel gehorchen:
P_1 = Zahl_1_1 * Zahl_2_1 P_2 = Zahl_1_2 * Zahl_2_2 P_3 = (Zahl_1_1 + Zahl_1_2) * (Zahl_2_1 + Zahl_2_2)In unserem Beispiel erechnet sich:
P_1 = 01234 * 00000 = 0 P_2 = 56789 * 98765 = 5608765585 P_3 = (01234 + 56789) * (00000 + 98765) = 5730641595Wie Sie sicherlich schon gemerkt haben, genau an dieser Stelle würde die Rekursion im Algorithmus ansetzen. Für P_1, P_2 und P_3 kann dasselbe Verfahren verwendet werden. Am Ende blieben nur noch kurze Zahlen zu Multiplizieren. So kann bei 2-stelligen Zahlen dann eine "echte" Muliplikation ausgeführt werden.
Was noch fehlt ist die Berechnungsregel, um die Zahlen wieder zusammenzusetzen:
Ergebnis = P_1 * 10 hoch 2N + (P_3 - P_2 - P_1) * 10 hoch N + P_2Wenn Sie die Rechnung durchführen, erhalten Sie genau 12193258259412, was dem gewünschtem Ergebnis entspricht.
Umsetzung in VBA
Wie schon zuvor erläutert, wird VBA durch die technischen Einschränkungen nicht die normalen Datentypen Long oder Double verwenden können. Wir werden den Datentyp für Zeichenketten 'String' verwenden, müssen dann aber das Addieren und Subtrahieren selbst implementieren. Schauen wir uns zunächst den Beispielcode näher an:
Public Function mlfpKaratsuba(First As String, Second As String) As String
Dim a As String
Dim b As String
Dim c As String
Dim d As String
Dim r As String
Dim x As String
Dim y As String
Dim z As String
Dim n As Long
Dim p As Long
' Length...
n = mlfhMax(Len(First), Len(Second))
n = n + n Mod 2
n = n / 2
' Check...
If n < 2 Then
' Return...
mlfpKaratsuba = CStr(CLng(CStr(0) & First) * _
CLng(CStr(0) & Second))
' Exit..
Exit Function
End If
' Decompose...
If 2 * n > Len(First) Then
a = Left(String(2 * n - Len(First), CStr(0)) & First, n)
b = Right(First, n)
Else
a = Left(First, n)
b = Right(First, n)
End If
If 2 * n > Len(Second) Then
c = Left(String(2 * n - Len(Second), CStr(0)) & Second, n)
d = Right(Second, n)
Else
c = Left(Second, n)
d = Right(Second, n)
End If
' Recurse...
x = mlfpKaratsuba(a, c)
y = mlfpKaratsuba(b, d)
z = mlfpKaratsuba(mlfhAdd(a, b), mlfhAdd(c, d))
' Calculate...
a = x & String(2 * n, CStr(0))
b = mlfhAdd(y, x)
b = mlfhSubstract(z, b)
b = b & String(n, CStr(0))
' Result...
r = mlfhAdd(a, b)
r = mlfhAdd(r, y)
' Return...
mlfpKaratsuba = r
End Function
In einem ersten Schritt ermitteln wir die Länge der Eingangsparameter 'First' und 'Second', die unsere zwei Zahlen darstellen sollen. Die Länge normalisieren wir so, dass diese durch 2 teilbar ist. Anschließend zerlegen wir die Zahlen in je gleich lange Teilzahlen und stellen diesen auch gleich die Nullen voran. Um die Produkte P_1, P_2 und P_3 (hier x, y und z) zu ermitteln, rufen wir unsere Funktion rekursiv auf. Zu beachten ist auch, dass P_3 ein Produkt zweier Summen ist. Die Funktion mlfhAdd() führt eine Addition zweier Zahlen als Zeichenkette durch.Auch zu Berechnung des Ergebnisses müssen wir bedenken, dass dort Additionen und Substraktionen enthalten sind. Die Potenz von 10 hoch N kann ganz einfach durch das Anhängen von Nullen geschehen.
An dieser Stelle muss übrigens noch erwähnt werden, dass der Code 'ganz frisch' ist. Sollte jemanden ein Fehler auffallen, dann freue ich mich über jede Nachricht.
Wir stellen Ihnen gerne unser Beispielprojekt 'Karatsuba mit Excel VBA' zur Verfügung. Der Code legt die Ergebnisse in Textdateien ab. Sie sind herzlich eingeladen, den Code zu verbessern, zu optimieren oder einfach uns nur eine Rückmeldung zu geben. Weitere Links zu dem Thema finden Sie folgend aufgeführt…
» Erläuterungen zum Karatsuba-Algorithmus bei Wikipedia, Deutsch
» RWTH Aachen, schneller Algorithmus der Woche, Deutsch
» Professor Anatolii Alexeevitch Karatsuba, Englisch
» Multiplication algorithm bei Wikipedia, Englisch
Blog
Neuigkeiten
