de
Seitenbanner
Menu
A-Z
  • Nachlesen
  • Grundlagen
  • Binäres Potenzieren
Nachlesen

Binäres Potenzieren

Beim binären Potenzieren (auch binäre Exponentiation oder Square and Multiply genannt) handelt es sich um eine effiziente Methode zur Berechnung von natürlichen Potenzen \(a^n\) eines Elements \(a\) und einer natürlichen Zahl \(n\).

Inhalt

Beschreibung des Verfahrens

Berechnung mithilfe der Rekursionsformel

Gegeben sei ein Element \(a\) sowie eine natürliche Zahl \(n \in \N\). Gemäß der Definition von Potenzen mit natürlichen Exponenten gilt:

\[ a^n = \underbrace{a \cdot a \cdot \ldots \cdot a}_{n \text{ Faktoren}}. \]

Anstelle der (sehr aufwendigen) Berechnung durch wiederholte Multiplikation mit dem Element \(a\) kann zur effizienten Berechnung der Potenz \(a^n\) die rekursive Formel

\[ a^n = \begin{cases} {\left( a^{\frac{n}{2}} \right)}^2 & \text{für gerade } n, \\[0.5em] a^{n-1} \cdot a & \text{für ungerade } n \end{cases} \]

verwendet werden. Diese führt die Berechnung der \(n\)-ten Potenz für gerade Exponenten auf die Berechnung der halben Potenz \(\frac{n}{2}\) und für ungerade Exponenten auf die Berechnung der Potenz \(n-1\) zurück. Für ungerade Exponenten \(n\) handelt es sich bei \(n-1\) stets um einen geraden Exponenten, der im nachfolgenden Schritt entsprechend halbiert wird. Hieraus resultiert, dass sich der Exponent der noch zu berechnenden Potenz nach jeweils maximal zwei Schritten halbiert. Für die Berechnung der \(n\)-ten Potenz sind somit höchstens \(\lceil 2 \cdot \log_2{n} \rceil\) Schritte vonnöten; im Gegensatz zu \(n-1\) Schritten bei sturem Ausmultiplizieren.

Die in der Formel verwendete Gleichheit \(a^n = {\left(a^{\frac{n}{2}}\right)}^2\) bzw. \(a^n = a^{n-1} \cdot a\) gilt aufgrund der Assoziativität der Multiplikation.

Allgemein gilt: Das Verfahren kann immer dann angewendet werden, wenn es sich bei \(a \in A\) um ein Element einer Halbgruppe \((A, \cdot)\) handelt, wobei \(\cdot\) die Multiplikation der Elemente aus \(A\) beschreibt. Hierunter fallen unter anderem die natürlichen, ganzen, rationalen, reellen oder komplexen Zahlen, aber beispielsweise auch Restklassen, Polynome, Matrizen und elliptische Kurven.

Da in jedem Schritt entweder quadriert oder mit \(a\) multipliziert wird, wird dieses Verfahren auch als Square and Multiply bezeichnet.

Berechnen mithilfe der Binärdarstellung des Exponenten

Zum Berechnen der Potenz \(a^n\) kann anstelle der rekursiven Formel auch die Binärdarstellung des Exponenten \(n\) verwendet werden, um zu entscheiden, wann quadriert und wann multipliziert werden muss. Hierzu wird die Binärdarstellung des Exponenten von links beginnend Ziffer für Ziffer betrachtet und ausgehend vom neutralen Element \(1\) der Multiplikation für jede \(1\) der Binärdarstellung des Exponenten zunächst quadriert und anschließend multipliziert (dargestellt als QM), für jede \(0\) ausschließlich quadriert (dargestellt durch Q). Da die Binärdarstellung des Exponenten stets mit einer \(1\) beginnt und somit als erster Schritt immer der Startwert 1 quadriert und anschließend mit \(a\) multipliziert wird, wird häufig das erste QM gestrichen und direkt der Startwert \(1^2 \cdot a = a\) verwendet.

Soll beispielsweise die Potenz \(a^{10}\) berechnet werden, wird zunächst die Binärdarstellung des Exponenten \(10\) gebildet: \({(1010)}_2\). Dies entspricht der folgenden Reihenfolge für das Quadrieren und Multiplizieren: QM Q QM Q. Nach Streichen des ersten QM verbleibt somit Q QM Q. Dies kann nun direkt in die Formel zum Ausrechnen der Potenz \(a^{10}\) überführt werden; es folgt:

\[ a^{10} = {\left( {\left( a^2 \right)}^2 \cdot a \right)}^2. \]

Dies kann alternativ auch wie folgt geschrieben werden:

\[ a \ \overset{\text{Q}}{\rightarrow}\ a^2 \ \overset{\text{Q}}{\rightarrow}\ a^4 \ \overset{\text{M}}{\rightarrow}\ a^5 \ \overset{\text{Q}}{\rightarrow}\ a^{10} \]

Die Verwendung der Binärdarstellung des Exponenten ist namensgebend für die Bezeichnungen binäres Potenzieren bzw. binäre Exponentiation.

Beispiel

Berechnung mithilfe der Rekursionsformel

Es soll die Potenz \(2^{23}\) berechnet werden. Gemäß der Rekursionsformel ergeben sich die folgenden Zwischenschritte:

\begin{align*} {2}^{23} &= {2}^{22} \cdot {2} \\[0.5em] {2}^{22} &= {\left({2}^{11} \right)}^2 \\[0.5em] {2}^{11} &= {2}^{10} \cdot {2} \\[0.5em] {2}^{10} &= {\left({2}^{5} \right)}^2 \\[0.5em] {2}^{5} &= {2}^{4} \cdot {2} \\[0.5em] {2}^{4} &= {\left({2}^{2} \right)}^2 \\[0.5em] {2}^{2} &= {\left({2}^{1} \right)}^2 \end{align*}

Hiermit kann das gewünschte Ergebnis ausgehend von der letzten Gleichung schrittweise berechnet werden:

\begin{align*} {2}^{2} &= 4 \\[0.5em] {2}^{4} &= 4^2 = 16 \\[0.5em] {2}^{5} &= 16 \cdot 2 = 32 \\[0.5em] {2}^{10} &= {32}^2 = 1\,024 \\[0.5em] {2}^{11} &= 1\,024 \cdot 2 = 2\,048 \\[0.5em] {2}^{22} &= {2\,048}^2 = 4\,194\,304 \\[0.5em] {2}^{23} &= 4\,194\,304 \cdot {2} = 8\,388\,608 \end{align*}

Berechnung mithilfe der Binärdarstellung des Exponenten

Es soll die Potenz \(2^{23}\) berechnet werden. Zunächst wird hierfür die Binärdarstellung des Exponenten 23 benötigt: \({(10111)}_2\). Aus dieser Darstellung ergibt sich die folgende Reihenfolge für das Quadrieren und Multiplizieren: QM Q QM QM QM. Nach Streichen des ersten QM verbleibt somit Q QM QM QM, womit für die Potenz \(2^{23}\) gilt:

\[ 2^{23} = {\left( {\left( {\left( 2^2 \right)}^2 \cdot 2 \right)}^2 \cdot 2 \right)}^2 \cdot 2 \]

Dieser Term kann nun schrittweise berechnet werden; es ergibt sich:

\begin{align*} 2^{23} &= {\left( {\left( {\left( 2^2 \right)}^2 \cdot 2 \right)}^2 \cdot 2 \right)}^2 \cdot 2 \\[0.5em] &= {\left( {\left( 4^2 \cdot 2 \right)}^2 \cdot 2 \right)}^2 \cdot 2 \\[0.5em] &= {\left( {\left( 16 \cdot 2 \right)}^2 \cdot 2 \right)}^2 \cdot 2 \\[0.5em] &= {\left( 32^2 \cdot 2 \right)}^2 \cdot 2 \\[0.5em] &= {\left( 1\,024 \cdot 2 \right)}^2 \cdot 2 \\[0.5em] &= 2\,048^2 \cdot 2 \\[0.5em] &= 4\,194\,304 \cdot 2 \\[0.5em] &= 8\,388\,608 \end{align*}

Unter Verwendung der alternativen Schreibweise ergibt sich:

\[ \begin{array}{c} 2 \ \overset{\text{Q}}{\rightarrow}\ 4 \ \overset{\text{Q}}{\rightarrow}\ 16 \ \overset{\text{M}}{\rightarrow}\ 32 \ \overset{\text{Q}}{\rightarrow}\ 1\,024 \\[0.5em] \overset{\text{M}}{\rightarrow}\ 2\,048 \ \overset{\text{Q}}{\rightarrow}\ 4\,194\,304 \ \overset{\text{M}}{\rightarrow}\ 8\,388\,608 \end{array} \]