Multiply two overflowing integers modulo a third
bit-manipulation, c
Solution
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).
Problem
Given three integers, `a`, `b`and `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?