Binäre Exponentiation

2024-04-22T08:09:12Z

84.119.16.74: Jetzt kann der Exponent eine beliebige vorzeichenbehaftete Ganzzahl sein.

Die '''binäre Exponentiation''' (auch '''Square-and-Multiply''' genannt) ist eine effiziente Methode zur Berechnung von [[Natürliche Zahl|natürlichen]] [[Potenz (Mathematik)|Potenzen]], also Ausdrücken der Form <math>x^k</math> mit einer natürlichen Zahl <math>k</math>.

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

== Motivation ==

Um <math>z = x^4</math> zu berechnen, kann man entweder <math>z = x \cdot x \cdot x \cdot x</math> ausrechnen (drei Multiplikationen) oder <math>y = x \cdot x</math>, <math>z = y \cdot y</math> (zwei Multiplikationen), also <math>z = (x^2)^2</math>.

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 Zahl]]en als auch für [[Matrix (Mathematik)#Matrizenmultiplikation|reellwertige Matrizen]], [[elliptische Kurve]]n und beliebige andere [[Halbgruppe]]n.

== Algorithmus ==

* Umwandlung des Exponenten <math>k</math> in die zugehörige [[Dualsystem|Binärdarstellung]].
* Ersetzen jeder '''0''' durch '''Q''' und jeder '''1''' durch '''QM.'''
* Nun wird '''Q''' als Anweisung zum [[Quadrat (Arithmetik)|Quadrieren]] und '''M''' als Anweisung zum [[Multiplikation|Multiplizieren]] aufgefasst.
* Somit bildet die resultierende [[Zeichenkette]] von links nach rechts gelesen eine Vorschrift zur Berechnung von <math>x^k</math>. Man beginne mit 1, quadriere für jedes gelesene '''Q''' das bisherige Zwischenergebnis und multipliziere es für jedes gelesene '''M''' mit <math>x</math>.

Da die Binärdarstellung von <math>k>0</math> immer mit der Ziffer 1 beginnt – und so ebenfalls die Anweisung mit '''QM''' beginnt –, ergibt sich für die erste Anweisung '''QM''' in jedem Fall das Zwischenergebnis <math>1^2 \cdot x=x</math>. Aus diesem Grund ergibt sich eine leicht vereinfachte Variante, bei der die erste Anweisung '''QM''' durch <math>x</math> ersetzt wird.

=== Beispiel (Algorithmus) ===

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 <math>x</math>, quadriere, multipliziere mit <math>x</math>, quadriere, multipliziere mit <math>x</math>“.

Formal sieht das Ganze so aus:
<math>\left( \left( (x^2)^2 \cdot x \right)^2 \cdot x \right)^2 \cdot x </math> bzw. sukzessive geschrieben:
: <math>
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}
</math>

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 <math>x</math> multipliziert.

=== Pseudocode (Algorithmus) ===

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.

{| class="wikitable toptextcells"
|- class="hintergrundfarbe5"
! Variante 1
! Variante 2
|-
|
<pre style="border:none;">
// Berechnet x^k
// b ... binäre Darstellung von k
// 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
</pre>
|
<pre style="border:none;">
// Berechnet x^k
// b ... binäre Darstellung von k
// 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
</pre>
|}

== 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 [[Russische Bauernmultiplikation|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 [[Quadratzahl|quadriert]]. Man streicht die Zeilen mit geradem Exponenten. Das Produkt der nichtgestrichenen rechten Zahlen ist die gesuchte Potenz.

=== Beispiel (alternativer Algorithmus) ===

{| class="wikitable"
|colspan="2" style="text-align:center"| 218
|-
|18
|<s>2</s>
|-
|9
|'''4'''
|-
|4
|<s>16</s>
|-
|2
|<s>256</s>
|-
|1
|'''65.536'''
|-
|Ergebnis
|262.144 (= '''4 · 65.536''')
|}

=== Pseudocode (alternativer Algorithmus) ===

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

Bestimmt werden soll <math>x^k</math>, ohne <math>k</math> in Binärdarstellung vorliegen zu haben.
{|
!width="50%" align="center"|Binäre Exponentiation
|-
|<syntaxhighlight lang="text">
// Berechnet x^k
// res … Resultat der Berechnung

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

== Rekursiver Algorithmus mit Herleitung ==

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

:<math>\begin{align}
a^n &= a^{2m+b} \\
&= (a^m)^2a^b.
\end{align}</math>

Der letzte Ausdruck beinhaltet lediglich
* eine Potenzierung mit einem Exponenten <math>m</math>, der nur noch etwa halb so groß wie <math>n</math> ist, welche rekursiv mit demselben Algorithmus berechnet werden kann,
* eine Quadrierung,
* eine Multiplikation,
* eine Potenzierung mit 0 oder 1 als Exponent.

Eine direkte Implementation in [[Haskell (Programmiersprache)|Haskell]] sähe wie folgt aus:
<syntaxhighlight lang="Haskell">
a^0 = 1
a^1 = a
a^2 = a*a
a^n = (a^m)^2 * a^b where (m, b) = n `divMod` 2
</syntaxhighlight>

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

Geringfügige Optimierungen, wie etwa die Umwandlung in eine [[Endrekursion|endrekursive]] Variante, führen im Wesentlichen zu oben genannten iterativen Algorithmen.

== Binäre Modulo-Exponentiation ==

Beim Rechnen [[Kongruenz (Zahlentheorie)|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.
Dieses Verfahren wird beispielsweise bei [[RSA-Kryptosystem|RSA-Verschlüsselung]] angewendet.

=== Beispiel ===

{| class="wikitable"
|colspan="2" style="text-align:center"| 218 mod 39
|-
|18
|<s>2</s>
|-
|9
|'''4'''
|-
|4
|<s>16</s>
|-
|2
|<s>22</s> (= 256 mod 39)
|-
|1
|'''16''' (= 484 mod 39)
|-
|Ergebnis
|25 (= '''4 · 16''' mod 39 = 218 mod 39)
|}

== Laufzeitanalyse ==

Bei der einfachen und langsamen [[Potenz (Mathematik)|Potenzierung]] von <math>x^k</math> werden <math>(k-1)</math> Multiplikationen benötigt. Bei der binären Exponentiation wird die Schleife lediglich <math>\log_2(k)</math>-mal durchlaufen (<math>\log_2(k)</math> entspricht hierbei ungefähr der Länge der Zahl <math>k</math> 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 <math>O(\log(k))</math> Operationen (eventuell Langzahloperationen) benötigt, wogegen <math>O(k)</math> Operationen bei der einfachen Potenzierung zu Buche schlagen. <math>O</math> bezeichnet eine [[Landau-Symbol|asymptotische obere Schranke]] für das Laufzeitverhalten des Algorithmus. Wie man leicht einsieht, ist die binäre Exponentiation sehr viel [[Effizienz (Informatik)|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 <math>z = x^{15}</math> zu berechnen, kann man entweder gemäß binärer Exponentiation
:<math>z = \left( \left((x^2 \cdot x)^2 \cdot x \right)^2 \cdot x \right)</math>
berechnen (6 Multiplikationen), oder aber
:<math>z = y^3 = y \cdot y^2</math> mit <math>y = x^5 = x \cdot (x^2)^2</math>
(insgesamt 5 Multiplikationen). Übersichtlicher schreibt man das, indem man nur die Folge der Exponenten der berechneten Potenzen aufschreibt, hier 1, 2, 4, 5, 10, 15, wobei jede der Zahlen Summe zweier vorangehender Zahlen der Folge ist; solche Folgen heißen [[Additionskette]]n. Ein Beispiel mit größerer Ersparnis ist der Exponent 367, für den man nacheinander die Potenzen mit den Exponenten 1, 2, 3, 5, 10, 20, 23, 43, 86, 172, 344, 367 berechnet, wobei die relativ aufwendig berechnete 23. Potenz zweimal verwendet wird: unmittelbar danach und ganz am Schluss. Dadurch werden gegenüber der binären Exponentiation drei Multiplikationen eingespart (11 statt 14).

Trotzdem ist in vielen Fällen die binäre Exponentiation das optimale Verfahren, weil die Berechnung der günstigsten Reihenfolge (also der kürzesten Additionskette) meist sehr viel aufwendiger ist als die Multiplikationen selbst, von denen man einige einspart. Anders ist es nur, wenn die Multiplikationen selbst sehr aufwendig sind (z. B. sehr große [[Matrix (Mathematik)|Matrizen]]) oder wenn viele Basen mit demselben Exponenten potenziert werden sollen.

== Implementierung in C++ ==

Es wird <math>0^0 := 1</math> verwendet, wie in der Funktion <code>pow</code> aus der [[Standard Template Library|STL]]. Statt <code>int</code> kann jeder ''vorzeichenbehaftete'' ganzzahlige Datentyp verwendet werden, falls nötig. Zur Vereinfachung der Darstellung fehlt eine Überprüfung auf Overflow und Underflow. Für negative Exponenten werden die Zwischenschritte positiv exponentiert und das Gesamtergebnis dann reziprok genommen, was eine höhere Präzision und bessere Performance ergibt.
<syntaxhighlight lang="c++">
// b: basis
// e: Exponent
template<std::floating_point Fp, std::signed_integral Int>
Fp bin_exp( Fp b, Int e )
{
Fp result = 1.0;
make_unsigned_t<Int> uE = e >= 0 ? e : -e;
auto next = [&] { uE >>= 1, b *= b; };
for( ; uE; next() )
{
for( ; !(uE % 2); next() );
result *= b;
}
return e >= 0 ? result : 1.0 / result;
}</syntaxhighlight>

== Literatur ==

* [[Donald E. Knuth]]: ''[[The Art of Computer Programming]].'' Vol 2. Addison-Wesley, 1998 (Section 4.6.3, S. 461).
* Jörg Arndt, Christoph Haenel: ''Pi. Algorithmen, Computer, Arithmetik.'' 2. Auflage. Springer, Berlin 2000, ISBN 3-540-66258-8, S. 120–121.

{{SORTIERUNG:Binare Exponentiation}}
[[Kategorie:Potenz (Mathematik)]]
[[Kategorie:Computerarithmetik]]
[[Kategorie:Zahlentheoretischer Algorithmus]]

Wikipedia (Deutsch) – Lokale Kopie - Benutzerbeiträge [de]

Binäre Exponentiation