Multiple/Division dilemma in equation

Question

I need to compute this equation in C/C++:

Click to copy

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:

Click to copy

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.

Answer 1

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

Long multiplication:

Click to copy

  (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:

Click to copy

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