In Excel mit sehr großen Zahlen rechnen – Teil 3 – Multiplikation

Nachdem wir nun eigene Berechnungsroutinen für die beiden Grundrechenarten „Addieren“ und „Subtrahieren“ für sehr große Zahlen implementiert haben (siehe hierzu meine beiden vorherigen Beiträge „In Excel mit sehr großen Zahlen rechnen – Teil 1 – Addition“ und „In Excel mit sehr großen Zahlen rechnen – Teil 2 – Subtraktion“), können wir nun eine VBA Funktion zur Multiplikation großer Zahlen erstellen.

Der hierfür verwendete Algorithmus stützt sich auf den „Karatsuba Algorithmus“. Ich hatte zwar schon dazu einen Artikel in meinem Blog auf meiner Softwareseite geschrieben, diesen Artikel hier im Excel Ticker Blog aber noch nicht übertragen. Deshalb an dieser Stelle nochmals ein paar Worte zur Funktionsweise vom Karatsuba Algorithmus.

Funktionsweise vom Karatsuba Algorithmus

Die Grundidee vom Algorithmus ist es, einerseits Multiplikationen durch Additionen und Verschiebeoperationen zu ersetzen und andererseits durch Aufteilung der zu multiplizierenden Zahlen Rechenschritte einzusparen. 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.

Der Karatsuba Algorithmus ist zwar nicht das schnellste Verfahren zur Multiplikation sehr großer ganzzahliger Zahlen, aber dafür recht einfach zu implementieren. Ein schnellerer Algorithmus ist übrigens der Schönhage-Strassen-Algorithmus, der auf einer schnellen Variante der diskreten Fourier-Transformation basiert. Wenn ich Zeit habe, werde ich mal eine VBA Implementierung von diesem Algorithmus ausprobieren.

Zurück zu Karatsuba; nehmen wir mal an, dass wir die in oberer Abbildung gezeigten zwei Ganzzahlen X und Y multiplizieren möchten. In der Abbildung habe ich zur Verdeutlichung absichtlich ein Leerzeichen zwischen den Ziffern von X und Y eingefügt.

In einem ersten Schritt wird die größte Länge (Anzahl der Ziffern) der jeweiligen Zahlen bestimmt, hier 20 Ziffern für X. Damit die Aufteilung der Zahlen in zwei gleich lange Zahlenblöcke erfolgen kann, muss die Länge durch 2 teilbar sein, was hier der Fall ist. Falls dem nicht so wäre, würden wir die Länge um 1 erhöhen. Beiden Zahlen werden, wenn nötig, so viele Nullen vorangestellt, dass beide Zahlen dieselbe Länge haben. Im oberen Beispiel ist das Y, dem zwei Nullen vorangestellt wurden, damit eine Länge von 20 erreicht wird.

Nun kann die Aufteilung in jeweils 10 Ziffern lange Zahlen (eigentlich sind es ja Zeichenketten) erfolgen. Wir erhalten somit für beispielsweise für X die Werte X_Links = X_L = 9876256719 und X_Rechts = X_R = 8712349865.

Für die Berechnung von P_3 müssen allerdings zuvor die „linken“ und „rechten“ Teile von X und Y zusammenaddiert und dann erst multipliziert werden. Das ergibt dann P_3 = (X_Links + X_Rechts) * (Y_Links + Y_Rechts).

Sind einmal die Teilprodukte berechnet, lassen sich deren Ergebnisse wieder so zusammen setzen, dass das Gesamtergebnis der Multiplikation von X * Y berechnet wird. Die Formel hierfür lautet dann Ergebnis = P_1 * 10 hoch N + (P_3 – P_2 – P1) * 10 hoch (N/2) + P_2. Der Wert N entspricht der Länge der Eingangswerte, also 20 Ziffern.

Wie Sie sicherlich schon bemerkt haben, enthält der Karatsuba Algorithmus einige Additionen und Subtraktionen. Genau dort werden dann die Funktionen zum Einsatz kommen, die ich in den zwei Artikeln zuvor beschrieben habe. Multiplikationen im Karatsuba Algorithmus werden durch einen rekursiven Aufruf erledigt werden. Um beispielsweise X_Links * X_Rechts zu berechnen, würden wir dann für diese zwei Teilzahlen dieselben zuvor beschriebenen Schritte durchlaufen. Das kann solange erfolgen, bis die Zahlen so kurz geworden sind, dass diese sich wieder über eine „einfache“ Multiplikation berechnen lassen.

Multiplikation von großen Zahlen in Excel

Schauen wir uns nun den Code zur Multiplikation von Zahlen an. In einem ersten Schritt wird im Code die größte Länge der Eingangsparameter ermittelt und in der Variable „lngLength“ abgelegt. Anschließend erfolgt eine Prüfung, ob die Länge beider Zahlen zusammen kleiner der Länge ist, die noch zu einem berechenbaren Ergebnis über eine einfache Multiplikation führt. Falls dem so ist, wird aber trotzdem nochmals der Fehlercode abgefragt und falls dieser ungleich Null ist, die einfache Multiplikation widerrufen.

Anschließend erfolgt die Prüfung der Länge, ob diese durch 2 teilbar ist und die Berechnung der halben Länge. Danach werden die Eingangsvariablen X und Y in je zwei gleich lange Anteile aufgeteilt und in den Variablen strArgs_X_L und strArgs_X_R sowie strArgs_Y_L und strArgs_Y_R abgelegt. Parallel dazu erfolgt die Prüfung, ob Nullen vorangestellt werden müssen.

Da wir ja später für P_3 die Produkte der einzelnen Anteile von X und Y brauchen, werden diese Werte schon mal ausgerechnet und in den Variablen strTemp_A_1 und strTemp_A_2 abgelegt. Hier findet auch erstmalig der Aufruf der Funktion „mlfhAdd(…)“ statt, die die Berechnung mit Zeichenketten durchführt und in Teil 1 der Artikelserie vorgestellt wurde.

Anschließend werden die Teilprodukte P_1, P_2 und P_3 durch den rekursiven Aufruf der Funktion „mlfhMultiply(…)“ berechnet. Und schließlich werden die letzten Bestandteile zur Bildung des Gesamtergebnisses berechnet. Übrigens, das Potenzieren mit einer 10-er Potenz kann ganz einfach durch das Anhängen der entsprechenden Anzahl von Nullen erledigt werden.

Das war’s auch schon. Der nächste Artikel wird dann eine Methode zum Potenzieren von Ganzzahlen vorstellen, die auch wiederum Karatsuba einsetzen wird. Somit nähern wir uns dem Ursprungsproblem, nämlich der Berechnung von 80 hoch 200 in Excel. Abschließend ein paar weiterführende Links zum Thema.

• Erläuterungen zum Karatsuba-Algorithmus bei Wikipedia, Deutsch
• Erläuterungen zum Schönhage-Strassen-Algorithmus bei Wikipedia, Deutsch
• RWTH Aachen, schneller Algorithmus der Woche, Deutsch
• Professor Anatolii Alexeevitch Karatsuba, Englisch
• Multiplication algorithm bei Wikipedia, Englisch
• Artikel auf meiner Softwareseite von Februar 2009, Deutsch