LNUM.PRODUCT

Nachdem ich in meinen vorherigen Artikeln die zwei LAMBDA-Funktionen LNUM.SUM und LNUM.SUBTRACT zum Addieren und Subtrahieren großer Zahlen in Excel vorgestellt hatte, war ich neugierig geworden, ob die Implementierung einer Funktion zur Multiplikation sehr großer Zahlen als rein formelbasierte Lösung ebenfalls möglich ist. Vorab – ja das geht und Excel rechnet sogar Hunderte von Multiplikationen großer Zahlen in akzeptabler Geschwindigkeit durch.

Dieser Artikel stellt die LAMDA-Funktion LNUM.PRODUCT vor, die zwei sehr großer Zahlen in Excel multipliziert, ohne auf externe Bibliotheken, wie z.B. Add-Ins, zurückzugreifen.

Große Zahlen multiplizieren

Angenommen, es liegen die beiden Zahlen 99 995 492 198 785 672 356 und 7 392 345 623 648 574 als Text in den Zellen B2 und B3 eines Arbeitsblattes in Excel vor. Multipliziere ich diese beiden Zahlen über eine einfache Excel-Formel, sind ab der 16. Stelle die Werte auf Null gesetzt, wie in folgender Abbildung zu sehen.

Es muss also eine andere Lösung her. Es gibt verschiedene Algorithmen, um eine Multiplikation von sehr großen Zahlen durchzuführen und dabei möglich wenig Rechenschritte und somit Zeit zu verbrauchen. Ein sehr schneller Algorithmus ist beispielsweise der Schönhage-Strassen-Algorithmus, der auf einer diskreten Fourier-Transformation basiert. Eine Fourier-Transformation in Excel nur mit Formeln zu implementieren, dürfte jedoch äußerst kompliziert sein, sofern es überhaupt machbar wäre.

Ein älterer und nicht (mehr) ganz so schneller Algorithmus ist der Karatsuba-Algorithmus, der die Multiplikation durch Additionen und Verschiebeoperationen ersetzt und gleichzeitig über das Aufteilen der zu multiplizierenden Zahlen einiges an Rechenschritten einspart. Ein großer Vorteil des Algorithmus ist zudem, dass dieser sich rekursiv anwenden lässt. Also wie für eine LAMBDA-Funktion gemacht, weshalb ich den Karatsuba-Algorithmus hier verwenden werde.

Schauen wir uns folgende Abbildung an, die die einzelnen Schritte im Algorithmus anhand der in unserem Beispiel aufgeführten Zahlen visualisiert.

In einem ersten Schritt wird das Maximum aus den Längen der beiden Zahlen X und Y bestimmt. In diesem Fall ist die 20. Da später die Zahlen aufgeteilt werden, muss die Länge immer durch 2 teilbar sein. Ist dies nicht der Fall, wird auf den ermittelten Wert eine 1 addiert.

Damit die beiden Zahlen gleich lang sind, werden diese mit Führungsnullen aufgefüllt und jeweils geteilt, sodass die Anteile in die Variablen XR, XL, YR und YL abgelegt werden können. R steht für den rechten Anteil und L den linken Anteil der Zahlen.

Im nächsten Schritt ist aus den jeweiligen Anteilen eine Summe zu berechnen, die in den Variablen XS und YS abgelegt werden. Da die anteiligen Zahlen ja sehr groß sein können, muss zur Berechnung der Summen eine Funktion zur Verfügung stehen, die große Zahlen addiert. Das wäre dann die bereits implementierte LAMBDA-Funktion LNUM.SUM.

Es folgen drei Teilmultiplikationen, die in den Variablen PA, PB und PC abgelegt werden. Da auch diese Zahlen sehr groß sein können, kann hier wieder die Funktion LNUM.PRODUCT zum Einsatz kommen. Unsere Funktion zur Multiplikation wird dann rekursiv aufgerufen.

Schließlich müssen die Teilberechnungen wieder zusammengesetzt werden, was über die Formel F in der Abbildung geschieht. In der Implementierung werden wir später für die Teilberechnungen zusätzliche Hilfsvariablen innerhalb der Formel verwenden.

LNUM.PRODUCT

Die Syntax der Funktion LNUM.PRODUCT ist recht einfach, denn es braucht nur eine Angabe zu den beiden Zahlen, die in Textform vorliegen müssen:

=LNUM.PRODUCT(Value1;Value2)

Zunächst ermitteln wir den Wert N, um die beiden Zahlen aufzuteilen. Danach füllen die Zahlen mit Nullen auf und erzeugen jeweils ein Array aus den beiden Zahlen.

Die gleichlautenden Formeln zur Berechnung von N in den Zelle B3 bzw. C3 lauten:

=LET(Value1;B2;Value2;C2;
     M;MAX(LÄNGE(Value1);LÄNGE(Value2));
     N;M+REST(M;2);N)

Die LET-Formel ermittelt in der Hilfsvariable M die maximale Länge der beiden Zahlen, setzt N gleich M und addiert eine Eins, sofern denn M ungerade ist. Setzen wir nun Führungsnullen vor die beiden Zahlen. Wir erhalten in B4 und C4:

=LET(Value1;B2;Value2;C2;N;B3;X;WIEDERHOLEN(0;N-LÄNGE(Value1))&Value1;X)
=LET(Value1;B2;Value2;C2;N;C3;Y;WIEDERHOLEN(0;N-LÄNGE(Value2))&Value2;Y)

Wie zu sehen, wird die Anzahl der Führungsnullen durch die Differenz der Länge zu N bestimmt. Erstellen wir nun die dynamischen Arrays ab Zeile 5. Die beiden Formeln in B5 und C5 lauten:

=LET(Value1;B2;Value2;C2;N;B3;
     X;TEIL(WIEDERHOLEN(0;N-LÄNGE(Value1))&Value1;
       SEQUENZ(2;1;1;N/2);N/2);X)
=LET(Value1;B2;Value2;C2;N;C3;
     Y;TEIL(WIEDERHOLEN(0;N-LÄNGE(Value2))&Value2;
       SEQUENZ(2;1;1;N/2);N/2);Y)

Die Funktion SEQUENZ erzeugt ein dynamisches Array mit zwei Zeilen und einer Schrittweite von N/2, was in unserem Beispiel 10 entspricht. SEQUENZ generiert somit ein Array mit den Werten {1;11}. Die Funktion TEIL extrahiert dann 10 Zeichen ab den Positionen 1 und 11. Und, wir haben hier schon mal einen Teil der Formeln aus B4 und C4 in die Formeln in B5 und C5 übernommen.

Führen wir das Verschachteln fort und fügen die Berechnung von N ebenfalls hinzu. Wir erhalten somit in B5 und C5 die Formeln:

=LET(Value1;B2;Value2;C2;
     M;MAX(LÄNGE(Value1);LÄNGE(Value2));
     N;M+REST(M;2);
     X;TEIL(WIEDERHOLEN(0;N-LÄNGE(Value1))&Value1;
       SEQUENZ(2;1;1;N/2);N/2);X)
=LET(Value1;B2;Value2;C2;
     M;MAX(LÄNGE(Value1);LÄNGE(Value2));
     N;M+REST(M;2);
     Y;TEIL(WIEDERHOLEN(0;N-LÄNGE(Value2))&Value2;
       SEQUENZ(2;1;1;N/2);N/2);Y)

Diese beiden Formeln, die nur noch als Eingangsparameter die zwei Zahlen aus Zeile 2 verwenden, liefern jetzt X und Y jeweils als Arrays und sind die Basis für die weiteren Berechnungen.

Der nächste Schritt besteht darin, die Variablen XR, XL, YR und YL zu ermitteln. Das ist recht einfach, denn wir brauchen nur aus den Arrays die entsprechenden Werte über die INDEX-Funktion zu extrahieren. Und, um für XS und YS die Summen zu bilden, verwenden wir die bereits implementierte Funktion LNUM.SUM.

B7 =LET(X;B5#;XL;INDEX(X;1;1);XL)
B8 =LET(X;B5#;XR;INDEX(X;2;1);XR)
B9 =LET(Y;C5#;YL;INDEX(Y;1;1);YL)
B10=LET(Y;C5#;YR;INDEX(Y;2;1);YR)

B11=LET(XL;B7;XR;B8;XS;LNUM.SUM(XL;XR;8);XS)
B12=LET(YL;B9;YR;B10;YS;LNUM.SUM(YL;YR;8);YS)

Folgende Abbildung zeigt den derzeitigen Zustand.

Nun wäre es an der Zeit, die Variablen PA, PB und PC zu berechnen, die sich aus den Multiplikationen der anderen Werte ergeben:

PA=XL*YL=LNUM.PRODUCT(XL;YL)
PB=XR*YR=LNUM.PRODUCT(XR;YR)
PC=XS*YS=LNUM.PRODUCT(XR;YR)

Da wir aber noch gerade dabei sind, die Funktion LNUM.PRODUCT zu implementieren, können wir die Funktion zum jetzigen Zeitpunkt noch nicht verwenden. Somit berechnen wir die Werte erstmal manuell, z.B. anhand des Windows Taschenrechners oder anhand dieser Website.

Der nächste Schritt ist die Formel zur Berechnung des Gesamtergebnisses zu implementieren. Diese lautet PA*10^N+(PC-PB-PA)*10^(N/2)+PB. Wie zu sehen, beinhaltet diese zwei Subtraktionen. Wir können die Formel aber umschreiben in PA*10^N+(PC-(PB+PA))*10^(N/2)+PB und reduzieren somit die Anzahl der Subtraktionen auf eine. Es erscheint zudem sinnvoll, an dieser Stelle ein paar Hilfsvariablen einzuführen:

TA=PA+PB
TB=PC-TA & WIEDERHOLEN(0;N/2)
TC=PB+TB
TR=TC+(PA & WIEDERHOLEN(0;N))

Um die Zehnerpotenzen zu ermitteln, müssen wir beachten, dass es sich um große Zahlen handelt, weshalb wir dies in Textform über die Funktion WIEDERHOLEN erledigen. Zum Addieren und Subtrahieren greifen wir auf die LAMBDA-Funktionen LNUM.SUM und LNUM.SUBTRACT zurück.

Wir erhalten dann folgende Formeln:

TA=LET(PA;B13;PB;B14;LNUM.SUM(PA;PB;8))
TB=LET(N ;B3 ;PC;B15;TA;B16;LNUM.SUBTRACT(PC;TA;8)&WIEDERHOLEN(0;N/2))
TC=LET(PB;B14;TB;B17;LNUM.SUM(PB;TB;8))
TR=LET(N ;B3 ;TC;B18;PA;B13;LNUM.SUM(TC;PA&WIEDERHOLEN(0;N);8))

Das Ergebnis präsentiert sich nun wie folgt, wo dann TR das Gesamtergebnis darstellt.

Es sei noch angemerkt, dass LNUM.SUBTRACT für TB in Zelle B17 annimmt, dass der Wert in PC immer größer oder gleich dem Wert in TA ist. Ich nehme an, das dürfte generell der Fall sein; jedenfalls habe ich keine Werte gefunden, wo dem nicht so ist. Sollte sich meine Annahme jedoch als falsch herausstellen, würde LNUM.PRODUCT einen Fehler zurückgeben, denn mindestens eine Berechnung hätte ein negatives Vorzeichen, was nicht weiterverarbeitet werden kann. Die Formel müsste dann angepasst werden, um einen solchen Fall abzudecken.

Abschließend brauchen wir nur noch die Formeln zu einer einzigen Formel zusammensetzen. Und es ist sinnvoll, eine Überprüfung von N vorzunehmen. Denn ist die Anzahl der Stellen in den Zahlen sehr gering, beispielsweise 4, können wir eine einfache Excel-Multiplikation der Zahlen vornehmen. Das ergibt dann als LAMBDA-Formel:

=LAMBDA(Value1;Value2;
 LET(M;MAX(LÄNGE(Value1);LÄNGE(Value2));
     N;M+REST(M;2);
     WENN(N<5;PRODUKT(--Value1;--Value2);
          LET(X ;TEIL(WIEDERHOLEN(0;N-LÄNGE(Value1))&Value1;
                 SEQUENZ(2;1;1;N/2);N/2);
              Y ;TEIL(WIEDERHOLEN(0;N-LÄNGE(Value2))&Value2;
                 SEQUENZ(2;1;1;N/2);N/2);
              XL;INDEX(X;1;1);
              XR;INDEX(X;2;1);
              YL;INDEX(Y;1;1);
              YR;INDEX(Y;2;1);
              XS;LNUM.SUM(XL;XR;8);
              YS;LNUM.SUM(YL;YR;8);
              PA;LNUM.PRODUCT(XL;YL);
              PB;LNUM.PRODUCT(XR;YR);
              PC;LNUM.PRODUCT(XS;YS);
              TA;LNUM.SUM(PA;PB;8);
              TB;LNUM.SUBTRACT(PC;TA;8)&WIEDERHOLEN(0;N/2);
              TC;LNUM.SUM(PB;TB;8);
                 LNUM.SUM(TC;PA&WIEDERHOLEN(0;N);8)))))

Die Formel verwendet bereits rekursiv ihren Namen LNUM.PRODUCT. Damit diese Formel bzw. Funktion getestet werden kann, muss entsprechend der Name LNUM.PRODUCT im Namensmanager angelegt und die Formel dem Namen zugewiesen werden, da ansonsten Excel die Fehlermeldung #NAME? ausgibt.

Fazit

LAMBDA-Funktionen erweisen sich als sehr mächtig und die Möglichkeiten (fast) unendlich. Was mich betrifft, habe ich noch ganz viele Ideen, was an weiteren Funktionen implementiert werden kann. Zudem plane ich eine dedizierte Website zu LAMBDA-Funktionen.

Happy Exceling :-)