Gegeben drei ganze Zahlen, a. b und c mit a,b <= c < INT_MAX ich berechnen müssen (a * b) % c aber a * b kann überlaufen, wenn die Werte zu groß sind, was das falsche Ergebnis gibt.Multiply zwei überquellenden ganzen Zahlen modulo eine dritte
Gibt es eine Möglichkeit, dies direkt durch Bit-Hacken zu berechnen, d. H. Ohne einen Typ zu verwenden, der für die fraglichen Werte nicht überläuft?
Karatsuba-Algorithmus wird hier nicht wirklich benötigt. Es reicht aus, die Operanden nur einmal zu teilen.
Sagen wir der Einfachheit halber, dass Ihre Zahlen 64-Bit-Ganzzahlen ohne Vorzeichen sind. Sei k = 2^32. Dann
a=a1+k*a2
b=b1+k*b2
(a1+k*a2)*(b1+k*b2) % c =
a1*b1 % c + k*a1*b2 % c + k*a2*b1 % c + k*k*a2*b2 % c
Jetzt kann a1*b1 % c sofort berechnet werden, könnte der Rest abwechselnd berechnet wird durch x <<= 1 und x %= c 32 oder 64-mal (seit Durchführen (u * v)% c = ((u% c) * v)% c). Dies könnte scheinbar überlaufen, wenn c >= 2^63. Das Schöne ist jedoch, dass dieses Paar von Operationen nicht wörtlich ausgeführt werden muss. Entweder x < c/2 und dann müssen Sie nur eine Verschiebung (und es gibt keinen Überlauf) oder x >= c/2 und
2*x % c = 2*x - c = x - (c-x).
(und es gibt keinen Überlauf wieder).
Einige der wichtigsten Compiler bieten einen 128-Bit-Integer-Typ, mit dem Sie diese Berechnung ohne Überlauf durchführen können.
Muss in die gleiche Klasse wie Ivella gehen: http://StackOverflow.com/Questions/14857702/specific-modular-multiplication-algorithm –
Nein, ich reduziere nur meine Probleme, bis sie wie Hausaufgaben klingen ... Katabusa scheint ziemlich beteiligt Ich hatte gehofft, dass es einige offensichtliche Bit-Hacken gab, die ich vermisste (wie das '(a% c) * (b% c)% c', das im Link erwähnt wird, was aber nicht auf mein Problem zutrifft ...) – pascal
@MatsPetersson Wenn ein