Binäre Exponentiation

Die binäre Exponentiation (auch Square & Multiply genannt) ist eine effiziente Methode zur Berechnung von natürlichen Potenzen, also Ausdrücken der Form xk mit einer natürlichen Zahl k.

Dieser Algorithmus wurde bereits um ca. 200 v. Chr. in Indien entdeckt und ist in einem Werk namens Chandah-sûtra niedergeschrieben.

Inhaltsverzeichnis

Motivation

Um z = x4 zu berechnen, kann man entweder z = x \cdot x \cdot x \cdot x ausrechnen (drei Multiplikationen) oder y = x \cdot x, z = y \cdot y (zwei Multiplikationen), also z = (x2)2.

Ebenso können auch andere ganzzahlige Potenzen durch „fortgesetztes Quadrieren und gelegentliches Multiplizieren“ effizient berechnet werden.

Dieses Einsparen von Multiplikationen funktioniert sowohl für reelle Zahlen als auch für reellwertige Matrizen, elliptische Kurven und beliebige andere Halbgruppen.

Algorithmus

  • Umwandlung von k in die zugehörige Binärdarstellung.
  • Ersetzen jeder 0 durch Q und jeder 1 durch QM.
  • Nun wird Q als Anweisung zum Quadrieren und M als Anweisung zum Multiplizieren aufgefasst.
  • Somit bildet die resultierende Zeichenkette von links nach rechts gelesen eine Vorschrift zur Berechnung von xk. Man beginne mit 1, quadriere für jedes gelesene Q das bisherige Zwischenergebnis und multipliziere es für jedes gelesene M mit x.

Da die Binärdarstellung von k > 0 mit der Ziffer 1, also die Zeichenkette mit QM beginnt, ergibt sich folgende Variante des Algorithmus. Nach Initialisierung mit dem Wert 1 und Ausführung des führenden QM ergibt sich automatisch das Zwischenergebnis 1^2 \cdot x. Man kann also für Exponenten k > 0 das führende QM-Paar streichen und den letzten Schritt in obigem Algorithmus mit dem Wert x beginnen.

Beispiel

Sei k = 23. Die Binärdarstellung von 23 lautet 10111. Daraus ergibt sich nach den Ersetzungen QM Q QM QM QM. Nach dem Streichen des führenden QM-Paares hat man Q QM QM QM. Daraus können wir nun ablesen, dass der Rechenvorgang folgendermaßen auszusehen hat: „quadriere, quadriere, multipliziere mit x, quadriere, multipliziere mit x, quadriere, multipliziere mit x“.

Formal sieht das Ganze so aus: \left( \left( (x^2)^2 \cdot x \right)^2  \cdot x \right)^2  \cdot x bzw. sukzessive geschrieben:


x      \;\stackrel{\mathrm Q}\longrightarrow\;
x^2    \;\stackrel{\mathrm Q}\longrightarrow\;
x^4    \;\stackrel{\cdot x}  \longrightarrow\;
x^5    \;\stackrel{\mathrm Q}\longrightarrow\;
x^{10} \;\stackrel{\cdot x}  \longrightarrow\;
x^{11} \;\stackrel{\mathrm Q}\longrightarrow\;
x^{22} \;\stackrel{\cdot x}\longrightarrow\;
x^{23}

Man sieht am Beispiel, dass man sich mit Hilfe der binären Exponentiation einige Rechenschritte sparen kann. Anstatt von 22 Multiplikationen werden nur noch 7 benötigt, indem man viermal quadriert und dreimal mit x multipliziert.

Pseudocode

Der Algorithmus ist in zwei Varianten dargestellt. Variante 1 verwendet eine if-Bedingung um an den entsprechenden Stellen zu multiplizieren. Variante 2 baut die if-Bedingung implizit in den arithmetischen Ausdruck ein.

Variante 1 Variante 2
// Berechnet x^c
// b   ... binäre Darstellung von c
// res ... Resultat der Berechnung

function bin_exp(x,b)
  res = 1
  for i = n..0
    res = res^2
    if b_i == 1
      res = res * x  
    end-if
  end-for
  return res
end-function
// Berechnet x^c
// b   ... binäre Darstellung von c
// res ... Resultat der Berechnung
 
function bin_exp(x,b)
  res = 1
  for i = n..0
    res = res^2 * x^{b_i}
  end-for
  return res
end-function

Alternativer Algorithmus

Man kann das Verfahren für eine Berechnung von Hand auch so gestalten, dass man zunächst die Basis oft genug quadriert und anschließend die richtigen Zahlen miteinander multipliziert. Dann ähnelt es der russischen Bauernmultiplikation, welche die Multiplikation zweier Zahlen auf das Halbieren, Verdoppeln und Addieren von Zahlen zurückführt.

Dazu schreibt man den Exponenten links und die Basis rechts. Der Exponent wird schrittweise halbiert (das Ergebnis wird abgerundet) und die Basis schrittweise quadriert. Man streicht die Zeilen mit geradem Exponenten. Das Produkt der nichtgestrichenen rechten Zahlen ist die gesuchte Potenz.

Beispiel

218
18 2
9 4
4 16
2 256
1 65.536
Ergebnis 262.144 (= 4 · 65.536)

Pseudocode

Anders als bei dem vorherigen Ansatz werden hier die benötigten Potenzen von x direkt aufmultipliziert. Diese Variante bietet sich an, wenn die Potenz c nicht explizit in Binärdarstellung vorliegt. Zur Veranschaulichung kann die Gleichheit x^{23} = x^{16}\cdot x^{4} \cdot x^{2} \cdot x betrachtet werden

Bestimmt werden soll xc, ohne c in Binärdarstellung vorliegen zu haben

Binäre Exponentiation
 //Berechnet x^c
 //res ... Resultat der Berechnung

 function res = bin_exp(x,c)
   res = 1
   aktpot = x
   while c > 0
     if c mod 2 == 1
       res = res * aktpot
     end-if
     aktpot = aktpot^2
     c = c DIV 2 //Ganzzahlige Division (das Ergebnis wird abgerundet)
   end-while
   return res
 end-function

Rekursiver Algorithmus mit Herleitung

Jede natürliche Zahl n lässt sich eindeutig in n = 2m + b zerlegen, wobei b\in\{0,1\}. Aufgrund der Potenzgesetze ergibt sich

\begin{align}
a^n &= a^{2m+b} \\
    &= (a^m)^2a^b.
\end{align}

Der letzte Ausdruck beinhaltet lediglich

  • eine Potenzierung mit einem Exponenten m, der nur noch etwa halb so groß wie n ist, welche rekursiv mit dem selben Algorithmus berechnet werden kann,
  • eine Quadrierung,
  • eine Multiplikation,
  • eine Potenzierung mit 0 oder 1 als Exponent.

Eine direkte Implementation in Haskell, sähe wie folgt aus.

    a^0 = 1
    a^1 = a
    a^2 = a*a
    a^n = (a^m)^2 * a^b where (m, b) = n `divMod` 2

Die Funktion ^, die hier definiert wird, stützt sich also auf ein vorhandenes * für die Multiplikation, divMod für die Abspaltung der untersten Binärstelle des Exponenten und, rekursiv, sich selbst.

Geringfüge Optimierungen, wie etwa die Umwandlung in eine endrekursive Variante, führen im Wesentlichen zu oben genannten imperativen Algorithmen.

Binäre modulo-Exponentiation

Beim Rechnen modulo einer natürlichen Zahl ist eine leichte Modifikation anwendbar, die verhindert, dass die berechneten Zahlen zu groß werden: Man bildet nach jedem Quadrieren und Multiplizieren den Rest. Die zuvor vorgestellten Algorithmen können leicht durch diese Moduloperationen erweitert werden.

Beispiel

218 mod 39
18 2
9 4
4 16
2 22 (= 256 mod 39)
1 16 (= 484 mod 39)
Ergebnis 25 (= 4 · 16 mod 39 = 218 mod 39)

Laufzeitanalyse

Bei der einfachen und langsamen Potenzierung von xc werden (c − 1) Multiplikationen benötigt. Beim „Square & Multiply“ wird die Schleife lediglich log 2(c)-mal durchlaufen (log 2(c) entspricht hierbei ungefähr der Länge der Zahl c in der Binärdarstellung). In jedem Schleifendurchlauf kommt es zu einer Quadrierung (wobei die erste Quadrierung vernachlässigt werden kann) und eventuell einer Multiplikation. Asymptotisch werden O(log(c)) Operationen (eventuell Langzahloperationen) benötigt, wogegen O(c) Operationen bei der einfachen Potenzierung zu Buche schlagen. O bezeichnet eine asymptotische obere Schranke für das Laufzeitverhalten des Algorithmus. Wie man leicht einsieht, ist das „Square-&-Multiply“-Verfahren sehr viel effizienter als das einfache Verfahren. Dieser verringerte Anspruch an die Rechenleistung ist bei großen Basen und Exponenten enorm.

Ähnliche Algorithmen

Die Binäre Exponentiation muss nicht notwendig die „multiplikationssparendste“ Berechnungsart einer Potenz sein. Um beispielsweise z = x15 zu berechnen, kann man entweder gemäß binärer Exponentiation

z = \Big( \left((x^2 \cdot x)^2 \cdot x \right)^2 \cdot x \Big)

berechnen (6 Multiplikationen), oder aber

z = y^3 = y \cdot y^2

mit

y = x^5 = x \cdot (x^2)^2

(insgesamt 5 Multiplikationen).

Literatur

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Binäre modulo-Exponentiation — Die binäre Exponentiation ist eine effiziente Methode zur Berechnung von natürlichen Potenzen, also Ausdrücken der Form xk mit einer natürlichen Zahl k. Dieser Algorithmus wurde bereits um ca. 200 v. Chr. in Indien entdeckt und ist in einem Werk… …   Deutsch Wikipedia

  • Schnelle Exponentiation — Die binäre Exponentiation ist eine effiziente Methode zur Berechnung von natürlichen Potenzen, also Ausdrücken der Form xk mit einer natürlichen Zahl k. Dieser Algorithmus wurde bereits um ca. 200 v. Chr. in Indien entdeckt und ist in einem Werk… …   Deutsch Wikipedia

  • ModPower — Die binäre Exponentiation ist eine effiziente Methode zur Berechnung von natürlichen Potenzen, also Ausdrücken der Form xk mit einer natürlichen Zahl k. Dieser Algorithmus wurde bereits um ca. 200 v. Chr. in Indien entdeckt und ist in einem Werk… …   Deutsch Wikipedia

  • Schnelle Exponentation — Die binäre Exponentiation ist eine effiziente Methode zur Berechnung von natürlichen Potenzen, also Ausdrücken der Form xk mit einer natürlichen Zahl k. Dieser Algorithmus wurde bereits um ca. 200 v. Chr. in Indien entdeckt und ist in einem Werk… …   Deutsch Wikipedia

  • Abessinischen Bauernregel — Die Russische Bauernmultiplikation (auch Ägyptisches Multiplizieren oder Abessinische Bauernregel genannt) ist ein einfaches Verfahren zur Multiplikation zweier natürlicher Zahlen. Es war schon im Altertum bekannt, in Deutschland wurde es bis ins …   Deutsch Wikipedia

  • Bauernmultiplikation — Die Russische Bauernmultiplikation (auch Ägyptisches Multiplizieren oder Abessinische Bauernregel genannt) ist ein einfaches Verfahren zur Multiplikation zweier natürlicher Zahlen. Es war schon im Altertum bekannt, in Deutschland wurde es bis ins …   Deutsch Wikipedia

  • Russische Bauernmethode — Die Russische Bauernmultiplikation (auch Ägyptisches Multiplizieren oder Abessinische Bauernregel genannt) ist ein einfaches Verfahren zur Multiplikation zweier natürlicher Zahlen. Es war schon im Altertum bekannt, in Deutschland wurde es bis ins …   Deutsch Wikipedia

  • Russische Bauernregel — Die Russische Bauernmultiplikation (auch Ägyptisches Multiplizieren oder Abessinische Bauernregel genannt) ist ein einfaches Verfahren zur Multiplikation zweier natürlicher Zahlen. Es war schon im Altertum bekannt, in Deutschland wurde es bis ins …   Deutsch Wikipedia

  • Ägyptische Multiplikation — Die Russische Bauernmultiplikation (auch Ägyptisches Multiplizieren oder Abessinische Bauernregel genannt) ist ein einfaches Verfahren zur Multiplikation zweier natürlicher Zahlen. Es war schon im Altertum bekannt, in Deutschland wurde es bis ins …   Deutsch Wikipedia

  • Ägyptisches Multiplizieren — Die Russische Bauernmultiplikation (auch Ägyptisches Multiplizieren oder Abessinische Bauernregel genannt) ist ein einfaches Verfahren zur Multiplikation zweier natürlicher Zahlen. Es war schon im Altertum bekannt, in Deutschland wurde es bis ins …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”