Heute nun der vierte Teil meiner Serie zum Thema „In Excel mit großen Zahlen rechnen“, der eine Funktion zur effektiven Berechnung von Potenzen in Excel VBA vorstellen wird. Wenn wir von dem Ursprungsproblem (die Berechnung von 80 hoch 200 in Excel, siehe den ersten Teil der Artikelserie) ausgehen, benötigen wir spätestens und unabhängig von der Darstellung des Ergebnisses ab 80 hoch 160 eine Funktion, die mit großen Zahlen umgehen kann.
Die Berechnung von 80 hoch 200 entspricht insgesamt von 200 – 1 = 199 Multiplikation der Zahl 80 mal sich selbst. Eine Funktion zur Multiplikation großer Zahlen steht uns ja bereits zur Verfügung; diese hatte ich im dritten Teil der Artikelserie vorgestellt. Problematisch ist jedoch die hohe Anzahl an benötigten Multiplikationen, die zu einer hohen Rechenzeit führen. Insofern gilt es zu schauen, ob die Anzahl der Multiplikation reduziert werden kann und, wenn ja, wie dies in VBA implementiert werden kann.
Binäre Exponentiation
Wenn man im Internet nach Lösungen zu diesem Problem sucht, findet man sehr schnell das Verfahren der „Binären Exponentiation“, das bereits 200 v. Chr. In Indien entdeckt wurde und quasi als das Standardverfahren zur Reduktion der Anzahl der Multiplikationen gilt.
Obere Abbildung stellt das Verfahren schematisch dar. Das Prinzip ist eigentlich relativ einfach: Der Exponent wird in eine binäre Zahl umgewandelt, die Einsen in der binären Darstellung durch „QM“ und die Nullen durch „Q“ ersetzt. Hierbei steht „Q“ für Quadrieren, also Zahl hoch 2, und „M“ für Multiplizieren mit der Ursprungszahl. Die Folge von Q’s und M’s ergeben dann eine Rechenvorschrift. Und, die erste QM-Folge, von links aus gesehen, kann übersprungen werden.
Schauen wir uns das Beispiel in der Abbildung genauer an, welches die Berechnung von 3 hoch 200 zeigt. Der Exponent in binärer Darstellung entspricht „11001000“. Die erste „1“ streichen wir und erhalten somit die Folge „QMQQQMQQQ“.
Damit würde eine Funktion zur Berechnung von 3 hoch 200 in einem ersten Schritt quadrieren, also 3 hoch 2 = 3 mal 3 = 9. Der nächste Schritt wäre „M“, also das vorherige Ergebnis 9 multipliziert mit der Ursprungszahl 3, ergibt 27. Es folgt wieder ein „Q“, insofern quadrieren wir die Zahl 27 und erhalten 27 mal 27 = 729. Es folgt noch ein „Q“, also 729 mal 729 = 531441. Dieselbe Methodik wenden wir für die weiteren Q’s und M‘s an, bis wir das Ende der Zeichenkette erreicht haben.
Additionsketten zur Reduktion der Anzahl der Multiplikationen
Bei der Suche nach weiteren Möglichkeiten zur Reduktion der Anzahl der Multiplikationen hatte ich einen englischen Artikel bei der Wikipedia gefunden, der das aus meiner persönlichen Sicht sehr interessante Thema „Addition Chains“ behandelt. Sucht man dediziert nach dem Stichwort, findet man relativ schnell die Bachelorarbeit von Sander van der Kruijssen, die einerseits eine genaue Erläuterung der Additionsketten gibt und Methoden zum Suchen solcher vorstellt.
Was ist aber nun eine Additionskette? Eigentlich ganz einfach: eine solche beginnt üblicherweise mit Eins und jedes nächste Glied entspricht der als Summe zweier vorangegangener Zahlen. Beispielweise kann die Zahlenfolge {1, 2, 3, 6} als {1, 2 = 1 + 1, 3 = 2 + 1 und 6 = 3 + 3} formuliert werden.
Mathematisch gesehen, lässt sich jeder Exponent in einer Potenzrechnung in eine Additionskette zerlegen. Würde man insofern die kürzeste Additionskette finden, hätte man gleichzeitig die geringste Anzahl an Multiplikationen gefunden. Bezogen auf zuvor erwähnte Zahlenfolge würde dann die Berechnung von N ^ 6 dann der Berechnung von X = N ^ 2, Y = N * X und Z = Y ^ 2 = Endergebnis entsprechen.
Es lassen sich übrigens für ein und dieselbe Zahl mehrere Additionsketten finden. Schauen wir uns hierzu folgende Grafik an.
Beide Beispiele zerlegen die Zahl 200 in eine Additionskette, wobei das erste Beispiel ein Element mehr enthält als das zweite Beispiel. Beide Additionsketten könnten zur Berechnung von X hoch 200 verwendet werden, zweitere würde jedoch eine Multiplikation weniger enthalten. Und die zweite Kette entspricht der Reihenfolge aus der binären Exponentiation.
Dies heißt jedoch nicht, dass die binäre Exponentiation die kürzesten und optimalsten Additionsketten liefert; es ist eher so, dass sie nur eine „hinreichend“ kurze Additionskette liefert. Sander van der Kruijssen beschreibt in seiner Arbeit weitere Verfahren, wie die „Factor Method“, „Window Method“ oder die „Power Tree Method“. Für den interessierten Leser habe ich den Link zu seiner wirklich empfehlenswerten Arbeit am Ende des Artikels aufgeführt. Das Englisch ist meines Erachtens auch für diejenigen sehr gut verständlich, die nicht über tiefere Englisch Kenntnisse verfügen.
Zusammenfassend, eine allgemein gültige Methode, die für jede beliebige Ganzzahl die kürzeste Additionskette liefert, konnte bislang noch nicht gefunden werden. Es gibt jedoch Datenbanken bzw. Websites im Internet, die für ganzzahlige Exponenten die kürzesten Additionsketten zur Verfügung stellen.
Potenzieren von großen Zahlen in Excel
Nach dem kleinen Exkurs in die Mathematik, stellte sich für mich die Frage, wie ich die Funktion zum Potenzieren in VBA implementiere. Eine Liste aller kürzesten Additionsketten für einen Zahlenbereich zu führen wäre sicherlich zu aufwendig und es würden auch letztendlich nicht jegliche Exponenten abgedeckt werden. Da aber die binäre Exponentiation hinreichend genau und relativ einfach zu implementieren ist, habe ich mich für diese entschieden.
Zunächst brauchen wir aber eine zusätzlich Hilfsfunktion, die den Exponenten in eine binäre Darstellung umwandelt. In VBA existiert die Funktion Hex(), die eine Ganzzahl in eine hexadezimale Darstellung umwandelt. Danach ist es eigentlich recht einfach, die einzelnen hexadezimalen Ziffern in eine binäre Form zu überführen. Der Code zur Funktion „mlfhConvertToBinary(…)“ übernimmt diese Aufgabe.
Nun zum Code für die Funktion „mlfhPower(…)“ zum Potenzieren. In einem ersten Schritt wird geprüft, ob sich die Potenz nicht auf klassischem Wege berechnen lässt. Falls dies nicht geht oder ein Fehler produziert wird, wird zunächst der Exponent in eine binäre Form umgewandelt.
Anschließend erfolgt das Ersetzen der binären Ziffern, wie zuvor erläutert, durch Q’s und M’s. Die darauf folgende Schleife führt dann die Rechenregel aus und ruft die ja bereits implementierte Funktion zur Multiplikation von großen Zahlen auf.
Das war’s dann wieder auch; eine Rekursion der Funktion zum Potenzieren ist nicht notwendig und die Geschwindigkeit ist akzeptabel.
Zusammenfassend stehen und nun VBA Funktionen zum Addieren, Subtrahieren, Multiplizieren und Potenzieren zur Verfügung. Ich bin mir noch nicht ganz sicher, ob ich im nächsten Artikel das Add-In schon mal zusammenstelle oder erst Funktionen für das Dividieren und Wurzelziehen zur Verfügung stelle. Schauen wir mal. Abschließend ein paar weiterführende Links zum Thema.
