5

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?

pascal
  • 2,623
  • 2
  • 20
  • 30
  • 3
    Must be going to the same class as Ivella: http://stackoverflow.com/questions/14857702/specific-modular-multiplication-algorithm – Mats Petersson Feb 13 '13 at 16:43
  • No, I just reduce my problems until they sound like homework… Katabusa seems quite involved, I was hoping there was some obvious bit-hacking I missed (like the `(a % c) * (b % c) % c` mentioned in the link, which doesn't apply to my problem though…) – pascal Feb 13 '13 at 16:56
  • @MatsPetersson If a < c then a % c == a – Olaf Dietsche Feb 13 '13 at 17:14
  • 2
    possible duplicate of [Overflow: a\*a mod n](http://stackoverflow.com/questions/10076011/overflow-aa-mod-n) (Specifically, see [my answer](http://stackoverflow.com/a/10076069/129570) there). This is for squaring, but can trivially be adapted for arbitrary multiplication. – Oliver Charlesworth Feb 13 '13 at 17:29
  • http://stackoverflow.com/q/8733178/995714 – phuclv Aug 02 '15 at 17:50

2 Answers2

7

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).

n. m. could be an AI
  • 112,515
  • 14
  • 128
  • 243
0

Several of the major compilers offer a 128-bit integer type, with which you can do this computation without overflow.