How does Excel successfully round floating point numbers even though they are imprecise?

Question

For example, this blog says 0.005 is not exactly 0.005, but rounding that number yields the right result.

I have tried all kinds of rounding in C++ and it fails when rounding numbers to certain decimal places. For example, Round(x,y) rounds x to a multiple of y. So Round(37.785,0.01) should give you 37.79 and not 37.78.

I am reopening this question to ask the community for help. The problem is with the impreciseness of floating point numbers (37,785 is represented as 37.78499999999).

The question is how does Excel get around this problem?

The solution in this round() for float in C++ is incorrect for the above problem.

Answer 1

"Round(37.785,0.01) should give you 37.79 and not 37.78."

First off, there is no consensus that 37.79 rather than 37.78 is the "right" answer here? Tie-breakers are always a bit tough. While always rounding up in the case of a tie is a widely-used approach, it certainly is not the only approach.

Secondly, this isn't a tie-breaking situation. The numerical value in the IEEE binary64 floating point format is 37.784999999999997 (approximately). There are lots of ways to get a value of 37.784999999999997 besides a human typing in a value of 37.785 and happen to have that converted to that floating point representation. In most of these cases, the correct answer is 37.78 rather than 37.79.

Addendum
Consider the following Excel formulae:

=ROUND(37785/1000,2)
=ROUND(19810222/2^19+21474836/2^47,2)

Both cells will display the same value, 37.79. There is a legitimate argument over whether 37785/1000 should round to 37.78 or 37.79 with two place accuracy. How to deal with these corner cases is a bit arbitrary, and there is no consensus answer. There isn't even a consensus answer inside Microsoft: "the Round() function is not implemented in a consistent fashion among different Microsoft products for historical reasons." ( http://support.microsoft.com/kb/196652 ) Given an infinite precision machine, Microsoft's VBA would round 37.785 to 37.78 (banker's round) while Excel would yield 37.79 (symmetric arithmetic round).

There is no argument over the rounding of the latter formula. It is strictly less than 37.785, so it should round to 37.78, not 37.79. Yet Excel rounds it up. Why?

The reason has to do with how real numbers are represented in a computer. Microsoft, like many others, uses the IEEE 64 bit floating point format. The number 37785/1000 suffers from precision loss when expressed in this format. This precision loss does not occur with 19810222/2^19+21474836/2^47; it is an "exact number".

I intentionally constructed that exact number to have the same floating point representation as does the inexact 37785/1000. That Excel rounds this exact value up rather than down is the key to determining how Excel's ROUND() function works: It is a variant of symmetric arithmetic rounding. It rounds based on a comparison to the floating point representation of the corner case.

The algorithm in C++:

#include <cmath> // std::floor

// Compute 10 to some positive integral power.
// Dealing with overflow (exponent > 308) is an exercise left to the reader.
double pow10 (unsigned int exponent) { 
   double result = 1.0;
   double base = 10.0;
   while (exponent > 0) {
      if ((exponent & 1) != 0) result *= base;
      exponent >>= 1;
      base *= base;
   }
   return result;
}   

// Round the same way Excel does.
// Dealing with nonsense such as nplaces=400 is an exercise left to the reader.
double excel_round (double x, int nplaces) {
   bool is_neg = false;

   // Excel uses symmetric arithmetic round: Round away from zero.
   // The algorithm will be easier if we only deal with positive numbers.
   if (x < 0.0) {
      is_neg = true;
      x = -x; 
   }

   // Construct the nearest rounded values and the nasty corner case.
   // Note: We really do not want an optimizing compiler to put the corner
   // case in an extended double precision register. Hence the volatile.
   double round_down, round_up;
   volatile double corner_case;
   if (nplaces < 0) {
      double scale = pow10 (-nplaces);
      round_down  = std::floor (x * scale);
      corner_case = (round_down + 0.5) / scale;
      round_up    = (round_down + 1.0) / scale;
      round_down /= scale;
   }
   else {
      double scale = pow10 (nplaces);
      round_down  = std::floor (x / scale);
      corner_case = (round_down + 0.5) * scale;
      round_up    = (round_down + 1.0) * scale;
      round_down *= scale;
   }

   // Round by comparing to the corner case.
   x = (x < corner_case) ? round_down : round_up;

   // Correct the sign if needed.
   if (is_neg) x = -x; 

   return x;
}   

Answer 2

For very accurate arbitrary precision and rounding of floating point numbers to a fixed set of decimal places, you should take a look at a math library like GNU MPFR. While it's a C-library, the web-page I posted also links to a couple different C++ bindings if you want to avoid using C.

You may also want to read a paper entitled "What every computer scientist should know about floating point arithmetic" by David Goldberg at the Xerox Palo Alto Research Center. It's an excellent article demonstrating the underlying process that allows floating point numbers to be approximated in a computer that represents everything in binary data, and how rounding errors and other problems can creep up in FPU-based floating point math.

Answer 3

I don't know how Excel does it, but printing floating point numbers nicely is a hard problem: http://www.serpentine.com/blog/2011/06/29/here-be-dragons-advances-in-problems-you-didnt-even-know-you-had/