end-Iterator decrement definiert?
-
Außerdem würde ich pow_mod(b,e,m) auf mul_mod(a,b,m) stützen!
So ein
mul_mod(uint64_t b,uint64_t e,uint64_t m){ uint64_t result; __asm{mul…} __asm{mod…} return…
darf dann ruhig mal gebaut werden.
-
Außerdem würde ich %2 und /2 benutzen, der Kontext ist so furchtbar mathematisch, da mag ich im Kontext bleiben.
Das ist doch Quatsch. Weil das &1 da ganz klar fragt, ob das Bit gesetzt ist. Und nicht ob die Zahl durch zwei Teilbar ist, oder welchen Rest selbige Division hervorbringt. Daher verstehe ich nicht: warum die Bedeutung beider Operationen durcheinanderbringen?
-
Arcoth schrieb:
Das ist doch Quatsch. Weil das &1 da ganz klar fragt, ob das Bit gesetzt ist. Und nicht ob die Zahl durch zwei Teilbar ist, oder welchen Rest selbige Division hervorbringt. Daher verstehe ich nicht: warum die Bedeutung beider Operationen durcheinanderbringen?
Du hast offensichtlich nicht verstanden, wie und warum der Algorithmus funktioniert.
-
Kenner aller cppplonkers schrieb:
Arcoth schrieb:
Das ist doch Quatsch. Weil das &1 da ganz klar fragt, ob das Bit gesetzt ist. Und nicht ob die Zahl durch zwei Teilbar ist, oder welchen Rest selbige Division hervorbringt. Daher verstehe ich nicht: warum die Bedeutung beider Operationen durcheinanderbringen?
Du hast offensichtlich nicht verstanden, wie und warum der Algorithmus funktioniert.
Doch, den habe ich offensichtlich verstanden. Die Binärnotation gibt die einzelnen Faktoren des Produkts an, welches die endgültige Potenz ergibt:
Ich glaube eher, du hast einen kleinen Penis.
-
Tut mir leid, dass ich den alten Thread nochmal aufwärme - mir geht die Sache mit den Bits und der
for
-Schleife nicht aus dem Kopf, daher hier noch etwas philosophischer Senf dazu:define each schrieb:
Du iterierst über die Bits des Exponenten, warum kein for?
uint64_t result = 1; for (; exp; exp >>= 1) { if (exp & 1) result = (result*base)%mod; base *= base; } return result;
Grundsätzlich gute Frage, schließlich habe ich für ein sauberes
for
zur Iteration gestimmt. Bei dieser Anwendung passt es imho jedoch nicht. Gründe:exp
ist die Menge, und deren Bits die Elemente, über die "iteriert" wird. Soweit d'accord.Es fehlt jedoch die Laufvariable, bzw. der Iterator, davon lebt
for
eigentlich.exp
ist gleichzeitig Laufbedingung und die Menge, um die es geht. Das istfor
-untypisch.Unter "Iteration" verstehe ich, dass im Allgemeinen zunächst geplant ist, über alle Elemente drüberzugehen, zumindest über einen vorher definierten Bereich (wie im Beispiel mit den verschachtelten Schleifen, deren zweite erst beim 2. Element loslegt).
Wenn in einerfor
-Schleife vorher abgebrochen wird, dann nicht durch die Bedingung imfor
-Kopf, sondern im Allgemeinen durch eine weitere unabhängige Bedingung, die der Sauberheit wegen ein eigenesif
-Statement haben sollte.
Die Laufsteuerung der exp-for-Schleife dagegen stellt eine Iteration über alle Elmente nur vage in Aussicht, weil sie gleich einschränkt: "aber nur solange ich noch != 0 bin"; der tatsächliche Endpunkt ergibt sich dann erst im Laufe der Berechnungen.
Anders wäre es, wenn (unter viel größerem Aufwand) vorher die Position des größten 1-Bits bestimmt und damit eine Zähler-Laufvariable gefüttert würde. Das wäre dann typischfor
(aber eben nicht mehr elegant).Des weiteren sehe ich als ein Merkmal von "Iteration", dass die Elemente der Menge der Reihe nach an ihrem Platz entweder gelesen oder verändert werden. Die Größe der Menge ändert sich jedoch nicht.
Im Gegensatz dazu dasexp
-Beispiel: die Elemente werden zerstört bzw. die Menge an sich wird verkleinert.Fazit: In diesem Beispiel ist
while
wirklich besser. Weil es eine Schleife steuert: "Solange vom Kuchen noch was übrig ist, essen wir seine Rosinen der Reihe nach auf."