Dividing two integer without casting to double

Question

I have two integer variables, partial and total. It is a progress, so partial starts at zero and goes up one-by-one to the value of total.

If I want to get a fraction value indicating the progress(from 0.0 to 1.0) I may do the following:

double fraction = double(partial)/double(total);

But if total is too big, the conversion to double may lose information.

Actually, the amount of lost information is tolerable, but I was wondering if there is a algorithm or a std function to get the fraction between two values losing less information.

Answer 1

The obvious answer is to multiply partial by some scaling factor; 100 is a frequent choice, since the division then gives the percent as an integral value (rounded down). The problem is that if the values are so large that they can't be represented precisely in a double, there's also a good chance that the multiplication by the scaling factor will overflow. (For that matter, if they're that big, the initial values will overflow an int on most machines.)

Answer 2

Yes, there is an algorithm losing less information. Assuming you want to find the double value closest to the mathematical value of the fraction, you need an integer type capable of holding total << 53. You can create your own or use a library like GMP for that. Then

• scale partial so that (total << 52) <= numerator < (total << 53), where numerator = (partial << m)
• let q be the integer quotient numerator / total and r = numerator % total
• let mantissa = q if 2*r < total, = q+1 if 2*r > total and if 2*r == total, mantissa = q+1 if you want to round half up, = q if you want to round half down, the even of the two if you want round-half-to-even
• result = scalbn(mantissa, -m)

Most of the time you get the same value as for (double)partial / (double)total, differences of one least significant bit are probably not too rare, two or three LSB difference wouldn't surprise me either, but are rare, a bigger difference is unlikely (that said, somebody will probably give an example soon).

Now, is it worth the effort? Usually not.