CODEWITHSUNDEEP
c++calgorithmnumbers
Juraj Blaho
Juraj Blaho

Reputation: 13451

Avoiding overflow in integer multiplication followed by division

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?

Upvotes: 15

Views: 4937

Answers (4)

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272467

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.

Upvotes: 14

Alexandre C.
Alexandre C.

Reputation: 56956

In certain cases (historically LCG random number generators with selected constants), it is possible to do what you want, for some values of a and d.

This is called Schrage's method, see eg. there.

Upvotes: 0

CodesInChaos
CodesInChaos

Reputation: 108790

If the larger type is just 64 bits then the straight forward solution will most likely result in efficient code. On x86 CPUs any multiplication of two 32 bit numbers will give the overflow in another register. So if your compiler understands that, it can generate efficient code for Int64 result=(Int64)a*(Int64)b.

I had the same problem in C#, and the compiler generated pretty good code. And C++ compilers typically create better code than the .net JIT.

I recommend writing the code with the casts to the larger types and then inspect the generated assembly code to check if it's good.

Upvotes: 4

Mark B
Mark B

Reputation: 96241

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)

Upvotes: 4

Related Questions