Diskussion:Binäre Exponentiation

Letzter Kommentar: vor 1 Jahr von NeoUrfahraner in Abschnitt C++ Bitoperationen?

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

Ich vermisse diesen Ausschnitt aus schnelles Potenzieren:

"

Mathematische Herleitung

Bearbeiten

„Square & Multiply“ nutzt die Tatsache, dass eindeutig als geschrieben werden kann, wobei und . Die s sind also die Stellen von c in der Darstellung als Binärzahl.

Dies kann man wiederum umformen und erhält folgende Form: Der "Square & Multiply" Algorithmus bestimmt 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)) Beantworten


Laufzeit?

Bearbeiten

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?

Bearbeiten

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

Ich habe jetzt die Bitoperationen durch arithmetische Operationen ersetzt. Jeder moderne Compiler optimiert das bei vorzeichenlosen Zahlen sowieso. --NeoUrfahraner (Diskussion) 08:37, 25. Jan. 2023 (CET)Beantworten