Modulo Overflow



  • Hallo c-plusplus.net

    Hat sich schon jemand mit dem Modulo Overflow Problem befasst?
    Gesucht hab ich im Forum, gefunden nichts.

    Hat jemand dazu ein konkretes Vorgehen? Wenn möglich ohne BigInt.
    wachs

    Bei (un-)signed char verhält es sich anscheinend richtig

    uint m=200;
    unsigned char uc1=179,uc2=179,uc3=0;
    uc3=(uc1+uc2)%m;//=158
    uc3=(uc1*uc2)%m;//=41
    
    m=100;
    signed char sc1=89,sc2=89,sc3=0;
    sc3=(sc1+sc2)%m;//=78
    sc3=(sc1*sc2)%m;//=21
    

    Bei (un-)signed int verhält es sich NICHT richtig

    m=800000;
    uint ui1=100000,ui2=(UINT_MAX-100),ui3=0;
    ui3=(ui1+ui2)%m;//=99899
    ui3=(uint)(((ullong)ui1+(ullong)ui2)%m);//=667195
    ullong ull=((ullong)ui1+(ullong)ui2)%m; //=667195
    
    ui2=ui1-1;
    ui3=(uint)(((ullong)ui1*(ullong)ui2)%m);//=700000
    ull=((ullong)ui1*(ullong)ui2)%m;//=700000
    

    Und bei (un-)signed long long ist es irgendwie undefiniert

    m=800000;
    ullong ull1=10000000000,ull2=(ULLONG_MAX-100),ull3=0;
    
    //Könnte korrekt sein
    ull3=(ull1+ull2)%m;//=799899
    
    //Vermutlich falsches Ergebnis
    ull3=(ullong)fmod((double)ull1+(double)ull2,m);//=750592
    double d=fmod((double)ull1+(double)ull2,m);//=750592.0	
    
    ull2=ull1-1;
    //Könnte korrekt sein
    ull3=(ull1*ull2)%m;//=241920
    
    //Vermutlich falsches Ergebnis
    ull3=(ullong)fmod((double)ull1*(double)ull2,m);//=792832
    d=fmod((double)ull1*(double)ull2,m);//=792832.0
    


  • Kannst Du irgendwie in Worte fassen, was Du meinst, was "richtig" wäre? Ich hab irgendwie keine Lust, die Beispiele durchzurechnen.



  • Gibt es ein konkretes vorgehen, um nicht jeweils den nächsthöhren Datentyp in Anspruch zu nehmen. Bei ullong wäre das soweiso nicht möglich.

    wachs



  • Hmm, ich fürchte, da bleibt Dir nichts anderes übrig, als den nächstgrößeren Datentyp zu nehmen.



  • Es scheint so.

    So etwas hab ich schon.
    Z.B. für den int-Bereich hab ich's so gemacht.

    if((uint)(i1+i2)>(uint)(imax))
    {
      i3=i2-(imax-i1);
      res=((imax%m)+(i3%m))%m;
    }
    else 
      res=(i1+i2)%m;
    

    Wäre schön gewesen, wenn es etwas schöneres gäbe.

    Danke dir.

    Gruss wachs


  • Mod

    Ich unterstelle der EInfachkeit halber mal nichtnegative Werte.

    wachs schrieb:

    Modulo Overflow Problem

    modulo läuft nicht über.
    Für +,-,* gilt generell:
    ( a op b ) mod m = ( ( a mod m ) op ( b mod m ) ) mod m
    So kann z.B. bei der Addition Probleme leicht vermeiden:

    template <typename T>
    T add_modulo(T a, T b, T m) {
        a %= m;
        b %= m;
        if ( m - a > b )
            return a + b;
        else
            return a - m + b;
    }
    

    Bei Multiplikation wird es etwas schwieriger.
    Man könnte sie z.B. auf die Addition zurückführen:

    template <typename T>
    T mul_modulo(T a, T b, T m) {
        a %= m;
        b %= m;
        if ( a < b )
            std::swap( a, b );
        return !b ? 0 : add_modulo( b % 2 ? a : 0, mul_modulo( m - a > a ? a + a : a - m + a, b / 2, m ), m );
    }
    

    Ohne Anspruch auf Effizienz - Wenn ein größerer Datentyp zur Verfügung steht, um die Multiplikation ohne Überlauf durchführen zu können, ist der Umweg darüber zweiffellos vorzuziehen.

    wachs schrieb:

    m=800000;
    ullong ull1=10000000000,ull2=(ULLONG_MAX-100),ull3=0;
    
    //Könnte korrekt sein
    ull3=(ull1+ull2)%m;//=799899
    
    //Vermutlich falsches Ergebnis
    ull3=(ullong)fmod((double)ull1+(double)ull2,m);//=750592
    double d=fmod((double)ull1+(double)ull2,m);//=750592.0	
    
    ull2=ull1-1;
    //Könnte korrekt sein
    ull3=(ull1*ull2)%m;//=241920
    
    //Vermutlich falsches Ergebnis
    ull3=(ullong)fmod((double)ull1*(double)ull2,m);//=792832
    d=fmod((double)ull1*(double)ull2,m);//=792832.0
    

    Nun ja, ein bisschen Kopfrechnen sollte man schon können. Man sieht sofort, dass ull1 % m == 0 gilt. Und damit bei der Multiplikation 0 herauskommen sollte (wenn es denn ohne Überlauf/Ungenauigkeiten abliefe).



  • Danke camper

    Werde ich mir anschauen.

    Edit:
    Funktioniert bis jetzt einwandfrei. Auch einen Versuch mit ullong hab ich gemacht, und alles nachgerechnet. Stimmen.
    Die Multiplikation rekursiv zu machen finde ich eine gute Idee.
    Nochmals danke 👍

    Gruss wachs


Anmelden zum Antworten