Avoiding overflow in integer multiplication followed by division

Question

I have two integral variables a and b and a constant s resp. d. I need to calculate the value of (a*b)>>s resp. a*b/d. The problem is that the multiplication may overflow and the final result will not be correct even though a*b/d could fit in the given integral type.

How could that be solved efficiently? The straightforward solution is to expand the variable a or b to a larger integral type, but there may not be a larger integral type. Is there any better way to solve the problem?

Answer 1

If there isn't a larger type, you will either need to find a big-int style library, or deal with it manually, using long multiplication.

For instance, assume a and b are 16-bit. Then you can rewrite them as a = (1<<8)*aH + aL, and b = (1<<8)*bH + bL (where all the individual components are 8-bit numbers). Then you know that the overall result will be:

(a*b) = (1<<16)*aH*bH
      + (1<<8)*aH*bL
      + (1<<8)*aL*bH
      + aL*bL

Each of these 4 components will fit a 16-bit register. You can now perform e.g. right-shifts on each of the individual components, being careful to deal with carries appropriately.

Answer 2

I haven't exhaustively tested this, but could you do the division first, then account for the remainder, at the expense of extra operations? Since d is a power of two, all the divisions can be reduced to bitwise operations.

For example, always assume a > b (you want to divide the larger number first). Then a * b / d = ((a / d) * b) + (((a % d) * b) / d)