Geek asks and answers

Multiply two overflowing integers by the third

For three integers a, band cwith the help a,b <= c < INT_MAXI need to calculate (a * b) % c, but a * bcan overflow if the values ​​are too large, which gives the wrong result.

Is there a way to calculate this directly through bitax, i.e. without using a type that will not overflow for the corresponding values?

+5
source share
2 answers

The Karatsuba algorithm is not needed here. It is enough to split the operands only once.

Say, for simplicity, that your numbers are 64-bit unsigned integers. Let k = 2 ^ 32. Then

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

a1*b1 % c , x <<= 1 x %= c 32 64 ( (u * v)% c = ((u% c) * v) % ). , c >= 2^63. , . x < c/2, ( ), x >= c/2

2*x % c = 2*x - c = x - (c-x).

( ).

+7

128- , .

0

More articles:


All Articles