(a * b) / c MulDiv and delaing with overflow from intermediate multiplication

问题: I need to do the following arithmetic: long a,b,c; long result = a*b/c; While the result is guaranteed to fit in long, the multiplication is not, so it can overflow....

问题:

I need to do the following arithmetic:

long a,b,c;
long result = a*b/c;

While the result is guaranteed to fit in long, the multiplication is not, so it can overflow.

I tried to do it step by step (first multiply and then divide) while dealing with the overflow by splitting the intermediate result of a*b into an int array in size of max 4 ( much like the BigInteger is using its int[] mag variable).

Here I got stuck with the division. I cannot get my head around the bitwise shifts required to do a precise division. All I need is the quotient (don't need the remainder).

The hypothetical method would be:

public static long divide(int[] dividend, long divisor)

Also, I am not considering using BigInteger as this part of the code needs to be fast ( I would like to stick to using primitives and primitive arrays).

Any help would be much appreciated!

Edit: I am not trying to implement the whole BigInteger myself. What I am trying to do is to solve a specific problem (a*b/c, where a*b can overflow) faster than using the generic BigInteger.

Edit2: It would be ideal if it could be done in a clever way, by not getting overflow at all, some tips surfaced in the comments, but I am still looking for one that is correct.

Edit3: @Dave proposed a solution with GDC:

a * b / c = (a / gcd(a,c)) * (b / (c / gcd(a,c)))

While it clearly fails with a or b being prime numbers, what if the intermediate result is calculated in double and then casted to long like so:

a * b / c = ((double)a / gcd(a,c)) * (b / ((double)c / gcd(a,c)))

For now, it looks like it is resolving the precision issue. Am I missing something?

Edit4: I was wrong in my assumptions, the code with GDC would be wrong even in some cases where there is no overflow at all.


回答1:

Divide a/c and b/c into whole and fractional (remainder) parts, then you have:

a*b/c 
= c * a/c * b/c 
= c * (x/c + y/c) * (z/c + w/c)
= xz/c + xw/c + yz/c + yw/c where x and z are multiples of c

As such, you can trivially calculate the first three factors without overflow. In my experience, this is often enough to cover typical overflow cases. However, if your divisor is too large, such that (a % c) * (b % c) overflows, this method still fails. If that's a typical issue for you, you may want to look at other approaches (e.g. dividing both the biggest of a and b as well as c by 2 until you have no overflows anymore, but how to do that without introducing additional error due to biases in the process is non-trivial -- you'll need to keep a running score of the error in a separate variable, probably)

Anyway, the code for the above:

long a,b,c;
long bMod = (b % c)
long result = a * (b / c) + (a / c) * bMod + ((a % c) * bMod) / c;

If speed is a big concern (I'm assuming it is at least to some extent, since you're asking this), you may want to consider storing a/c and b/c in variables and calculating the mod through multiplication, e.g. replace (a % c) by (a - aDiv * c) -- this allows you to go from 4 divisions per call to 2.


回答2:

You can use the greatest common divisor (gcd) to help.

a * b / c = (a / gcd(a,c)) * (b / (c / gcd(a,c)))

Here's code to get the gcd.

static long gcd(long a, long b) 
{ 
  if (b == 0) 
    return a; 
  return gcd(b, a % b);  
} 

回答3:

You assume the following:

long a,b,c;
long result = a*b/c;
  • All 3 operands are of type long
  • The result is of type long
  • a * b may be greater and not suit into type long

Mathematical speaking:

(a * b) / c = (a / c) * b = a * (b / c)
  • a / c is surely of type long
  • b / c is surely of type long

As long as your assumption is correct (result is of type long), you need to divide the larger of (a) and (b) by (c) and do the multiplication afterwards to receive a result which is not bigger the type long.

But:

The type long holds no decimals. Therefore we need to save the remainder of the division as well.

(a * b) / c = (a / c) * b + (a % c) * b

We assume that (a % c) * b gets us a clear long-value and not a double-value. Alternatively we can use:

(a * b) / c = (b / c) * a + (b % c) * a

We assume that (b % c) * a holds no decimals.

Nevertheless @Jesper is right. As long as you don't plan to do this calculation several millions of times you should be fine with existing big types.

  • 发表于 2019-01-18 21:14
  • 阅读 ( 213 )
  • 分类:网络文章

条评论

请先 登录 后评论
不写代码的码农
小编

篇文章

作家榜 »

  1. 小编 文章
返回顶部
部分文章转自于网络,若有侵权请联系我们删除