Compare Floating Point Numbers
This week's tip comes from Bobby Orndorff of GrapeCity software. He's the Chief Architect for Spread.NET, and implemented the Spread Calculation Engine and the Chart component.
Floating point numbers have limited precision. This can lead to small approximation errors in calculations which, in turn, can cause unexpected results when comparing calculation results. For example, consider the following C# code, which multiples a number by its multiplicative inverse and then compares the calculated result with the expected result of one.
double x = 49.0;
double y = 1 / x;
double calculatedResult = x * y;
double expectedResult = 1.0;
bool areSame = calculatedResult == expectedResult;
We would expect areSame to be true, because the product of a number and its multiplicative inverse should always equal one. However, areSame will be false in the above code. The problem is that 1/49 cannot be represented exactly using the double data type. This introduces a small approximation error in y which in turn introduces a small approximation error in calculatedResult. This example demonstrates why it's unwise to perform an "exactly equals" comparison of floating point numbers.
To allow for small approximation errors in calculations, it's better to perform an "almost equals" comparison of floating point numbers which checks whether the numbers are close to each other. This involves checking whether the difference between the numbers is less than some epsilon.
The problem then becomes choosing an epsilon. Any fixed epsilon would likely be too small when comparing large numbers, or too large when comparing small numbers. Thus, it's desirable to choose a relative epsilon that is relative in magnitude to the numbers being compared. Note that the double data type uses 64 bits, with 1 bit for sign, 11 bits for exponent, and 52 bits for mantissa. If we choose epsilon by dividing one of the numbers by 2^n, a difference of less than epsilon will indicate that the numbers being compared agree about the first n bits of the mantissa. For example, consider an AlmostEqual method that compares the difference of the two numbers to the first number divided by 2^48.
public static bool AlmostEqual(double a, double b)
{
if (a == b)
{
return true;
}
return Math.Abs(a - b) < Math.Abs(a) / 281474976710656.0;
}
This method will return true when the two numbers match to about the first 48 bits of the mantissa (i.e., only disagree in about the last 4 bits of the mantissa). Note that the method has code to handle the special case when the two numbers are exactly equal. We can then rewrite our original code example using the AlmostEqual method in place of the == operator.
bool areSame = AlmostEqual(calculatedResult, expectedResult);
Now areSame will be true, indicating that caluclatedResult is close enough to expectedResult that any difference could easily be an approximation error due to limitations of the double data type.
Note that the above AlmostEqual method is not perfect. Zero will only compare almost equal to zero. Thus, the above AlmostEqual method doesn't account for approximation errors when one of the numbers being compared is zero.
Posted by Peter Vogel on 11/08/2011