Potenzieren

Kennst du die "Schachlegende"?

Schachlegende

Auf das erste Feld kommt 1 Reiskorn. Auf das zweite 2. Auf das dritte 4. Auf das vierte 8. Und so weiter. Immer doppelt so viele. Diese Reihe besteht aus den Zweierpotenzen: 2⁰=1, 2¹=2, 2²=4, 2³=8, 2⁴=16. Das Schachbrett hat 64 Felder, also kommen auf das letzte Feld 2⁶³=9223372036854775808 Reiskörner.

Potenzen sind vereinfachte Schreibweisen von besonders großen oder besonders kleinen Zahlen. Hinter 10² bzw. 10^2 verbirgt sich 10x10, also 100, hinter 10³ die 1000. Das Potenzieren von Zahlen bedeutet also, dass man eine Zahl so und so oft mit sich selbst malnimmt. Beispiele:

5^3 = 5 * 5 * 5 = 125
-2^4 = -2 * -2 * -2 * -2 = 16
aber auch
-3.5^3 = -3.5 * -3.5 * -3.5 = -42,875
5^-2 = 0.04 = 1/25
1.7^-2.73 = 0,23489536357
49^0.5 = 7

Man definiert: Jede beliebige Zahl hoch 0, also x^0 = 1.
Ein Potenz-Ausdruck besteht aus Basis und Exponent: Basis^Exponent

Ein Block existiert in Scratch jedoch nicht. Deshalb muss man, wenn man Potenzen berechnen will, eine solche Funktion selbst schreiben.

Es ist günstig, Fälle zu unterscheiden und diese verschieden zu berechnen:

1. Wenn der Exponent = 0 ist, dann ist das Ergebnis = 1.
2. Wenn der Exponent eine positive ganze Zahl ist, kann man einfach multiplizieren.
3. Wenn der Exponent eine negative ganze Zahl ist, dann berechnet man zuerst die Potenz für die positive Zahl und bildet vom Ergebnis den Kehrwert (wie im Beispiel oben: 5^-2 = 1/(5^2) = 0.04)
4. Wenn die Basis eine positive Zahl ist und der Exponent keine ganze Zahl, verwendet man den Logarithmus.
   Denn x^y = 10^{y * log(x)}
5. Wenn die Basis eine negative Zahl ist und der Exponent keine ganze Zahl, dann ist die Potenz nicht definiert.

Der 2. Fall: Der Exponent ist eine positive ganze Zahl

Definiere Potenz von (Basis) hoch (Exponent)
setze [Ergebnis v] auf (Basis)
wiederhole ((Exponent) - (1)) mal
setze [Ergebnis v] auf ((Ergebnis) * (Basis))
ende

Dieser Algorithmus benötigt (Exponent - 1) Multiplikationen. Geht das eigentlich auch anders? Mit weniger Multiplikationen? Ja!

Definiere Potenz von (Basis) hoch (Exponent)
setze [Ergebnis v] auf (1)
setze [Zweierpotenz v] auf (Basis)
setze [Exponent v] auf (Exponent)
wiederhole bis <(Exponent) = [0]>
falls <((Exponent) mod (2)) = [1]>, dann
setze [Ergebnis v] auf ((Ergebnis)*(Zweierpotenz))
setze [Exponent v] auf ((Exponent)-(1))
ende
falls <(Exponent)>[0]>, dann
setze [Zweierpotenz v] auf ((Zweierpotenz)*(Zweierpotenz))
setze [Exponent v] auf ((Exponent)/(2))
ende
ende

Dies sieht kompliziert aus und man fragt sich, was da eigentlich eingespart wird, aber tatsächlich wird dieser Algorithmus verwendet, wenn Potenzen mit großen Basen und großen Exponenten berechnet werden sollen. Er benötigt nur log₂(Exponent) Multiplikationen, denn er arbeitet so wie der Algorithmus für die Umwandlung einer Dezimalzahl in eine Binärzahl. 3^24 benötigt beispielsweise nicht 23 Multiplikationen, sondern nur 6 Multiplikationen (und zusätzlich 4 Divisionen durch 2, die ein Computer sehr schnell ausführen kann, und 2 Subtraktionen).

Die allgemeine Funktion

Definiere Potenz von (Basis) hoch (Exponent)
setze [Ergebnis v] auf (1)
falls <(Exponent) < [0]>, dann
falls <((Exponent) gerundet) = (Exponent)>, dann
setze [Zweierpotenz v] auf (Basis)
setze [Exponent v] auf (Exponent)
wiederhole bis <(Exponent) = [0]>
falls <((Exponent) mod (2)) = [1]>, dann
setze [Ergebnis v] auf ((Ergebnis)*(Zweierpotenz))
setze [Exponent v] auf ((Exponent)-(1))
ende
falls <(Exponent)>[0]>, dann
setze [Zweierpotenz v] auf ((Zweierpotenz)*(Zweierpotenz))
setze [Exponent v] auf ((Exponent)/(2))
ende
ende
sonst
falls <(Basis) > [0]>, dann
setze [Ergebnis v] auf ([10 ^ v] von ((Exponent) * ([log v] von (Basis))))
ende
falls <(Basis) < [0]>, dann
setze [Ergebnis v] auf [undefiniert]
ende
ende
ende
falls <(Exponent) < [0]>, dann
Potenz von (Basis) hoch ((0)-(Exponent))
setze [Ergebnis v] auf ((1) / (Ergebnis))
ende

Weiterführende Informationen

2⁶³ = 9223372036854775808
Berechnet man in Scratch 2⁶³ mit obigen Algorithmus, dann erhält man 9223372036854775810.00, was sicher nicht stimmt. Ein Nuller an der Einerstelle kann bei Zweierpotenzen nicht auftreten. (Dazu bedürfe es einer Multiplikation mit 5). Offenbar geht diese Rechnung über die Grenze der Genauigkeit von Scratch hinaus.
Um dennoch große Potenzen mit Scratch berechnen zu können, muss man Prozeduren zum Rechnen mit Strings schreiben. Im folgenden Beispielprojekt sind der obige Potenzierungsalgorithmus, ein Algorithmus zum Addieren von beliebig großen Zahlen, ein Algorithmus zum Dividieren einer beliebig großen Zahl durch eine Integer-Zahl und ein Algorithmus zum Multiplizieren zweier beliebig großer Zahlen (mit Ägyptischer bzw. Russischer Bauernmultipliaktion) implementiert.

Rechnen mit großen Zahlen

---

Code zum Einbinden ins Forum:
[wiki=de:Potenzieren]Potenzieren[/wiki]