Multiply two overflowing integers modulo a third

Question

Given three integers, a, band c with a,b <= c < INT_MAX I need to compute (a * b) % c but a * b can overflow if the values are too large, which gives the wrong result.

Is there a way to compute this directly through bithacks, i.e. without using a type that won't overflow for the values in question?

Answer 1

Karatsuba's algorithm is not really needed here. It is enough to split your operands just once.

Let's say, for simplicity's sake, 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

Now a1*b1 % c can be computed immediately, the rest could be computed by alternately performing x <<= 1 and x %= c 32 or 64 times (since (u*v)%c=((u%c)*v)%c). This could ostensibly overflow if c >= 2^63. However, the nice thing is that this pair of operations need not be performed literally. Either x < c/2 and then you only need a shift (and there's no overflow), or x >= c/2 and

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

(and there's no overflow again).