Schnelle Exponentiation

a^x in O(log x) Multiplikationen berechnen.

Idee: a in jeder Iteration mit sich selber multiplizieren. So entsteht die Folge:

a^1
a^2
a^4
a^8
...

a^x kann nun berechnet werden, indem bestimmte Zahlen aus dieser Folge miteinander multipliziert werden. Es gilt nämlich:

a^(x+y) = a^x * a^y

Jede Dezimalzahl lässt sich als Summe von 2er Potenzen darstellen (Binärdarstellung). Beispiel:

27 = 2^0 + 2^1 + 2^3 + 2^4 = 1 + 2 + 8 + 16

a^27 könnte man dementsprechend wie folgt schreiben:

a^(1+2+8+16) = a^1 * a^2 * a^8 * a^16

Das sind alles Glieder aus der obig beschriebenen Folge. Wenn man also die richtigen Glieder aus der Folge miteinander multipliziert erhält man a^x. Mit einem Beispiel lässt sich wohl besser als mit Worten zeigen, wie diese Glieder selektiert werden:

27 in binär = 1011
1 a^1 
1 a^2
0 a^4 (ignorieren)
1 a^8

Wenn wir also in jeder Iteration a mit sich selber multiplizieren entsteht automatisch die Folge a^1, a^2, a^4, ..., a^(2^n), und von denen multiplizieren wir alle die miteinander, wo in der Binärdarstellung vom Exponent eine 1 steht. Das ist insofern praktisch, als dass die Zahlen im Programmspeicher bereits als Binärzahlen vorliegen. Das kann man sich zunutze machen, die meisten Programmiersprachen bieten ein logisches UND & an, welches zwei Zahlen wie folgt verrechnet:

  1011 Zahl 1
& 0001 Zahl 2
= 0001 Resultat

Zugleich gibt es den Bitshift-Rechts Operator, der einfach alle Bits nach rechts schiebt:

1011 >> 1 = 0101

Diese zwei Mechanismen kombiniert man um herauszufinden, ob das aktuelle a^(2^n) Glied multipliziert werden muss:

1. Iteration: 1011 & 1 = 1 multiplizieren
2. Iteration: 0101 & 1 = 1 multiplizieren
3. Iteration: 0010 & 1 = 0 nichts tun
4. Iteration: 0001 & 1 = 1 multiplizieren
5. Iteration: 0000 & 1 = 0 (fertig wenn exponent 0 ist)

Folgend ein Beispiel Programm für die schnelle Exponentiation:

long res = 1;
while (x > 0) {
    if (x & 1) {
        res *= a;
    }
    x >>= 1;
    a *= a;
}

Beim naiven Ansatz von a^x würden x Multiplikationen ausgeführt; a * a * a ... und das x mal. Bei der schnellen Exponentiation verdoppelt sich der Exponent in jedem Schritt (statt sich nur um 1 zu erhöhen), deshalb ist man bereits nach log2(x) Schritten bei x angelangt; 1, 2, 4, 8, log2(x)-4 weitere Schritte, x. Hinzu kommen die Multiplikationen mit dem Resultat, nämlich für jede 1 in der Binärdarstellung vom Exponent eine Multiplikation, also maximal log2(x) zusätzliche Multiplikationen (Exponent besteht aus lauter Einsen). Das macht Total 2*log2(x) Multiplikationen, damit ist die Berechnungskomplexität im Worst CaseO(log x).