Diskussion:Binäre Exponentiation

schön wäre hier die Laufzeit in Landauscher Omega Notation der einzelnen Algorithmen.

Ich vermisse diesen Ausschnitt aus schnelles Potenzieren:

"

Mathematische Herleitung

„Square & Multiply“ nutzt die Tatsache, dass $a^{c}$ eindeutig als $a^{c}=a^{1\cdot b_{1}}\cdot a^{2\cdot b_{2}}\cdot a^{4\cdot b_{3}}\cdot \dots \cdot a^{2^{n-1}\cdot b_{n}}$ geschrieben werden kann, wobei $b_{i}\in \{0,1\}$ und $\sum _{i=1}^{n}b_{i}\cdot 2^{i-1}=c$. Die $b_{i}$s sind also die Stellen von c in der Darstellung als Binärzahl.

Dies kann man wiederum umformen und erhält folgende Form: $a^{c}=a^{b_{1}}(a^{b_{2}}(\dots (a^{b_{n-1}}(a^{b_{n}})^{2})^{2}\dots )^{2})^{2}$ Der "Square & Multiply" Algorithmus bestimmt $c$ derart, indem der geklammerte Ausdruck von innen nach außen berechnet wird. " (nicht signierter Beitrag von 85.216.120.226 (Diskussion | Beiträge) 17:50, 15. Jun. 2009 (CEST))

Laufzeit?

im worst-case x^((2^n)-1) benötigt man n multiplikationen und n quadrierungen. wenn man die quadrierung als multiplikation mit sich selbst betrachtet, ergibt das 2n*O(multiplikation(n stellen)), bei normaler multiplikation O(n^3), bei benutzung des Schönhage-Strassen-Algorithmus ergibt das O(n^2*ln(n)*ln(ln(n))). n ist dabei die bitlänge.

C++ Bitoperationen?

Warum werden im C++ Code unübersichtliche Bitoperationen verwendet und nicht einfach Modulo und Division wie im Pseudocode? --NeoUrfahraner (Diskussion) 18:15, 8. Nov. 2021 (CET)