Multiple/Division dilemma in equation

c, c++

Solution

You could implement the long arithmetic by hand, work with 32-bit blocks:

Long multiplication:

  (ax + b) * (cx + d)
= ac x^2 + (ad+bc) x + bd

  [ab]*[cd]=[efg]:

   //long long e,f,g
   g = (long long)b*d;
   f = (long long)a*d+b*c;
   e = (long long)a*c;
   //perform carry
   f += g>>32; g &= 0xFFFFFFFF
   e += f>>32; f &= 0xFFFFFFFF

School division, assuming unsigned arithmetic:

   [efg]/[hi]=[jkl]:

    [jk] = [ef]/[hi];
    r = [ef]-j*[hi];
    l = [rg]/[hi];
    if j > 0, result doesn't fit
    x = [kl];

If `a` and `b` are signed, fix the sign first and compute with absolute values, as suggestd by @Serge: if a or b is zero, `x=(-1)/c` otherwise, `sign(x)=sign(a)*sign(b)*sign(c)`

Problem

I need to compute this equation in C/C++: ``` x=(a*b-1)/c; ``` with a,b,c,x of type __int64 (a,b,c,x<10^13). In all cases, a,b,c is select to make x fit in __int64. However, a*b is very big that cause overflow and x is wrong. I try to seperate a*b by typecasting: ``` x=(__int64)(((double)a/c)*(double)b - 1.0/c); ``` This way, a/c is computed first and overflow error not occur. However, the problem is ((double)a/c)*(double)b sometimes have great value (about billions) and precision is reduced, so 1.0/c (very small) don't take any effect and cause an error within +-1. For example: (__int64)(((double)a/c)*(double)b=123456789.01 is more likely to become 123456789.0 and 1.0/c=0.02. In this case, there is an error of +1. Is there any way to compute x precise without external library such as Boost or Bignum? Even with error +-1 can screw up my code. Thanks in advance. By the way, I use Visual Studio 10.

Original source