overflow

[Fytch]

hallo

ich habe die möglichkeit, den rest von zahlen in N0 mit einem zweierpotenz-modul abzuspeichern (also z.b. ein unsigned int). nun habe ich zwei operanden und würde gerne herausfinden, ob die operation überlauft. bei additionen ist das noch trivial, da bin ich selbst drauf gekommen. wie ich das jedoch bei der multiplikation machen soll ist mir schleierhaft.
ein beispiel:
das modul ist 2^8 = 256
der term ist 50 * 10 = 500 -> 500 ≡ 244 mod 2^8
244 > 50; 244 > 10

der einfache trick wie bei der addition funktioniert also nicht mehr.

gibt es eine effiziente & schnelle möglichkeit (auf die langsamen bin ich schon selbst gekommen) zu prüfen, ob eine int-multiplikation überlaufen wird / ist?

gruss

[Jockelx]

Was ist denn die langsame Methode?
256 / a > b?

[Fytch]

also das verfahren für additionen ist trivial:
a + b = c → c ≥ max(a, b)

eins der langsamen verfahren für multiplikationen, das mir eingefallen ist wäre so ähnlich wie square & multiply, jedoch einfach eine "stufe" tiefer. beispiel:
7 * 5 = 7 * 2 * 2 + 7 usw.
das basiert darauf dass additionen nach der oben genannten methode sicher sind.

eine andere möglichkeit wäre es zu testen ob c durch a und durch b teilbar ist. da muss man aber aufpassen wenn das c durch das modul teilbar ist... da müsste sich vielleicht jemand äussern der von zahlentheorie ahnung hat.

eine quick&dirty methode wäre es noch das höchstwertigste bit der operanden herauszufinden, die positionen (besser gesagt, log2(wertigkeit)) zu addieren und zu schauen, ob die summe grösser ist als log2(modul). habs mal eben ausprobiert und es sieht aus, als wäre es sicher aber auch als würde es zu früh alarm schlagen:
8 * 16 = 128 (also noch im grünen bereich, schlägt nach der methode aber alarm)
15 * 31 = 465 (aus gutem grund!)

edit:

Jockelx schrieb:

Was ist denn die langsame Methode?
256 / a > b?

das verstehe ich nicht ganz. 256 / a ergibt immer 0 oder 1.

[Jockelx]

asfdlol schrieb:

Jockelx schrieb:

Was ist denn die langsame Methode?
256 / a > b?

das verstehe ich nicht ganz. 256 / a ergibt immer 0 oder 1.

Mmh, was?
Irgendwie hab ich wohl was übersehen...warum ist 256/50 = 1 oder = 0?

[Fytch]

Jockelx schrieb:

asfdlol schrieb:

Jockelx schrieb:

Was ist denn die langsame Methode?
256 / a > b?

das verstehe ich nicht ganz. 256 / a ergibt immer 0 oder 1.

Mmh, was?
Irgendwie hab ich wohl was übersehen...warum ist 256/50 = 1 oder = 0?

ahh, quatsch. frag mich nicht wie ich auf den blödsinn gekommen bin...
das dürfte schneller sein als meine ideen, werde ich mal testen. danke.