Potenzen effizient exakt berechnen

Potenzen $b^n$ mit der Basis $b$ und einem nicht negativen, ganzzahligen Exponenten $n$ stecken hinter manchen Phänomenen unseres Lebens. Sie spielen bei verzinsten Kontoguthaben und Ausbrüchen von Infektionskrankheiten wichtige Rollen. Ungetarnt begegnen sie uns im schulischen Mathematikunterricht. $b$ hoch $n$ bedeutet, dass wir $n$ Vorkommen der Zahl $b$ haben, die alle miteinander multipliziert werden.

Beispielsweise ist $b^{23} = b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b\cdot b$. Doch es ist nicht effizient, die Potenz tatsächlich so auszurechnen. Wer ein Rechenprogramm entwickelt oder schlicht Interesse am Thema hat, kann von Überlegungen zu einer schnelleren Methode profitieren.

Ich grübelte darüber und präsentiere mein Ergebnis hier anhand zweier Beispiele. Das erste Beispiel stelle ich ausführlich vor. So lässt sich nachvollziehen, wie die Methode funktioniert. In der Praxis kann man wie im zweiten Beispiel fast alle Schritte überspringen. Du findest auf dieser Seite auch Vergleiche von mir in Python programmierter rekursiver und iterativer Funktionen zum Potenzieren, jeweils naiv versus effizient.

Am Beispiel b hoch 23

Die Idee basiert auf der Darstellung des Exponenten als Dualzahl, auch Binärzahl genannt. Für das erste Beispiel $b^{23}$ ist

Wenn man auseinanderklamüsert, was die Binärdarstellung aus Nullen und Einsen in unserem Stellenwertsystem eigentlich bedeutet, so ist das:

Die $2^0$ am Ende ist schlicht eins. Alle anderen Zweien klammern wir eine nach der anderen aus:

Dann sieht die ganze Potenz inklusive der Basis $b$ so aus:

Wenn wir von rechts nach links die Potenzgesetze $x^{m+n}=x^m\cdot x^n$ und $x^{m\cdot n}=(x^m)^n$ im Wechsel anwenden, formen wir die ganze rechte Seite in ein geschachteltes Produkt um:

Beachte, dass sich das Muster 10111 noch immer in den Exponenten von $b$ findet. Alles andere sind regelmäßig gesetzte Klammern hoch zwei. Als nächstes ersetzen wir $b^0=1$ und $b^1=b$. So wird aus dem binären Muster 10111 des Exponenten das Muster b1bbb in den Basen.

Zu guter Letzt können wir uns die Multiplikation mit eins sparen. Es bleibt also:

Jeder Malpunkt dieser Gleichung steht für eine Multiplikation. Zudem entspricht jedes Quadrieren einer weiteren Multiplikation, denn $x^2=x\cdot x$. Zählt man Malpunkte und Quadrate auf der rechten Seite, stellt man fest: Um $b^{23}$ zu berechnen, benötigt die geschachtelte Klammerdarstellung nur 7 statt der 22 Multiplikationen bei der einfachen Herangehensweise aus der Einleitung.

Am Beispiel b hoch tausend

Als zweites Beispiel nehmen wir $b^{1000}$. Zu Beginn schreiben wir den dezimalen Exponenten $1000$ als Dualzahl auf:

Ohne Ausschweife machen wir aus seinem binären Muster 1111101000 das Muster bbbbb1b111 in den Basen eines geschachtelten Produkts von Quadraten

und entledigen uns noch der überflüssigen Multiplikationen mit eins:

Fertig. Wenn wir in der letzten Zeile die Malpunkte und Quadrate zählen, sehen wir: Uns genügen 14 Multiplikationen, um $b^{1000}$ zu berechnen. Nach Art der Einleitung bräuchten wir dagegen 999 Multiplikationen!

Gegenüberstellung mit Python, rekursiv

Potenzen zu berechnen ist eine übliche Aufgabe beim Erlernen der rekursiven Programmierung. Eine Funktion power, die der Potenz-Definition nahekommt, könnte in Python 3 wie folgt aussehen.

def power (b, n: int):
	if n < 0:
		raise ValueError ('unkosher exponent')
	elif n == 0:
		return 1
	else:
		return power (b, n - 1) * b

Ich bin versucht, bitte zuhause nicht nachmachen zu ergänzen. Doch ganz so schlimm ist es nicht. Du kannst die Funktion durchaus testen. Sie ist nur nicht für den Einbau in ein Programm von Bedeutung zu empfehlen. Meine Python-Installation bricht mit dieser Funktion die Berechnung von $2^{1000}$ auch ab, weil die Rekursionstiefe größer als erlaubt wird.

Man könnte aufgrund meiner obigen Ausführungen über das Umwandeln in Binärdarstellung und das Aufstellen eines geschachtelten Produktes von Quadraten befürchten, die deutlich effizientere Funktion sei dafür deutlich komplizierter. Ist sie aber kaum:

def power (b, n: int):
	if n < 0:
		raise ValueError ('unkosher exponent')
	elif n == 0:
		return 1
	elif n & 1:
		return power (b * b, n >> 1) * b
	else:
		return power (b * b, n >> 1)

Computer arbeiten nämlich intern sowieso binär und Programmiersprachen wie Python bringen zum Schubsen von Nullen und Einsen geeignete Operatoren mit. Zudem entspricht der rekursive Aufruf der Funktion schon dem Ausklammern.

Gegenüberstellung mit Python, iterativ

Iterativ droht selbst bei der naiven, langsamen Variante kein rascher Abbruch, weil Ressourcen überstrapaziert würden:

def power (b, n: int):
	if not isinstance (n, int) or n < 0:
		raise ValueError ('unkosher exponent')
	elif n == 0:
		return 1
	else:
		x = b
		while n > 1:
			x *= b
			n -= 1
		return x

Für ausgewachsene Exponenten ist aber die im Artikel vorgestellte und iterativ wie folgt umgesetzte Methode viel schneller.

def power (b, n: int):
	if not isinstance (n, int) or n < 0:
		raise ValueError ('unkosher exponent')
	elif n == 0:
		return 1
	else:
		x = 1
		while n > 1:
			if n & 1:
				x *= b
			b *= b
			n >>= 1
		return x * b

Hinweis zum Schluss: Lässt man den Computer mit Gleitkommazahlen als Basis rechnen – also ungenau –, können die naiven und die effizienten Funktionen zu abweichenden Ergebnissen gelangen. Aufgrund der unterschiedlichen Rechenwege wird dann an verschiedenen Stellen gerundet.