Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Binäre Exponentiation aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Binäre Exponentiation

Die binäre Exponentiation ist eine effektive Methode zur Berechnung von ganzzahligen Potenzen, also Ausdrücken der Form $x^k$ mit $k\; \backslash in\; \backslash mathbb\{Z\}$.

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

Algorithmus

* Umwandlung von k in die zugehörige Binärdarstellung.
* Ersetzen jeder 0 durch Q und jeder 1 durch QM.
* Streichen des führenden QM-Paares.
* Nun wird Q als Anweisung zum Quadrieren und M als Anweisung zum Multiplizieren aufgefasst.
* Somit bildet der resultierende String von links nach rechts gelesen eine Vorschrift zur Berechnung von $x^k$.

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 der beiden führenden QM lautet der String 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:
$\backslash left(\; \backslash left(\; (x^2)^2\; \backslash cdot\; x\; \backslash right)^2\; \backslash cdot\; x\; \backslash right)^2\; \backslash cdot\; x$ bzw. sukzessive geschrieben: $x^2,\; x^4,\; x^5,\; x^\{10\},\; x^\{11\},\; x^\{22\},\; 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 mehr 7 benötigt, indem man viermal quadriert und dreimal mit x multipliziert.

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 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

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 den Rest.

Beispiel

Literatur

Donald_E._Knuth: The Art of Computer Programming. Vol 2. Addison Wesley, 1998 (Seite 399)
* Jörg Arndt, Christoph Haenel: Pi. Algorithmen, Computer, Arithmetik. 2. Auflage. Springer, Berlin 2000 (Seite 120-121) ISBN 3-540-66258-8

       VIDEO-NEWS UND ANGEBOTE