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.


  • Mod

    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.


  • Mod

    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:
    x100101_2=x100000_2x100_2x1_2x ^{100101\_2} \quad = \quad x ^ {100000\_2} x ^ {100\_2} x ^ {1\_2}

    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 ist for -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 einer for -Schleife vorher abgebrochen wird, dann nicht durch die Bedingung im for -Kopf, sondern im Allgemeinen durch eine weitere unabhängige Bedingung, die der Sauberheit wegen ein eigenes if -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 typisch for (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 das exp -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."


Anmelden zum Antworten