CODEWITHSUNDEEP
c++floating-pointdouble
André Puel
André Puel

Reputation: 9179

Dividing two integer without casting to double

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.

Upvotes: 4

Views: 559

Answers (3)

Daniel Fischer
Daniel Fischer

Reputation: 183888

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.

Upvotes: 1

JayC
JayC

Reputation: 7141

If you want a precise representation of the fraction, you'd have some sort of structure containing the numerator and the denominator as integers, and, for unique representation, you'd just factor out the greatest common divisor (with a special case for zero). If you are just worried that after repeated operations the floating point representation might not be accurate enough, you need to just find some courses on numerical analysisas that issue isn't strictly a programming issue. There are better ways than others to calculate certain results, but I can't really go into them (I've never done the coursework, just read about it).

Upvotes: 0

James Kanze
James Kanze

Reputation: 153909

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

Upvotes: 7

Related Questions