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.
