dato tre numeri interi, a, b e c con a,b <= c < INT_MAX ho bisogno di calcolare (a * b) % c ma a * b può overflow se i valori sono troppo grandi, che dà il risultato sbagliato.moltiplicare due numeri interi traboccante modulo un terzo
C'è un modo per calcolarlo direttamente tramite bithacks, vale a dire senza utilizzare un tipo che non verrà sovrascritto per i valori in questione?
L'algoritmo di Karatsuba non è davvero necessario qui. È sufficiente dividere i tuoi operandi solo una volta.
Diciamo, per semplicità, che i numeri sono interi senza segno a 64 bit. Sia k = 2^32. Poi
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
Ora a1*b1 % c può essere calcolato immediatamente, il resto potrebbe essere calcolato alternativamente eseguendo x <<= 1 e x %= c 32 o 64 volte (dato che (u * v)% c = ((u% c) * v)% c). Questo potrebbe apparentemente traboccare se c >= 2^63. Tuttavia, la cosa bella è che questa coppia di operazioni non deve essere eseguita alla lettera. In entrambi i x < c/2 e quindi è necessario solo un turno (e non c'è overflow), o x >= c/2 e
2*x % c = 2*x - c = x - (c-x).
(e non c'è ancora nessun overflow).
Molti dei principali compilatori offrono un tipo intero a 128 bit, con il quale è possibile eseguire questo calcolo senza overflow.
Deve andare alla stessa classe di Ivella: http://stackoverflow.com/questions/14857702/specific-modular-multiplication-algorithm –
No, ho solo ridotto i miei problemi finché non sembrano compiti a casa ... Katabusa sembra piuttosto coinvolto , Speravo che ci fosse un po 'di evidente hacking del bit che mi mancava (come il '(a% c) * (b% c)% c' menzionato nel link, che però non si applica al mio problema ...) – pascal
@MatsPetersson Se a