Modulo Overflow

wachs

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

SG1

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

wachs

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

SG1

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

wachs

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

camper

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

wachs

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