Comparing doubles - an old old problem

The problem of comparing two doubles occurs in so many situation, I am sure that in some dev circles, it probably has got the name “the double trouble”. I am referring to the problem where you have to compare two doubles for equality, and based on the result (i.e., based on if they are equal or not), the code either kills a demon or self-destroys itself (put your own example here). In iterative algorithms, these situations are quite common. Searching through my code-base, I seem to have used these checks in the following situations:

• Matrix and Vector operations
• In a routine for reducing a symmetric matrix to tridiagonal matrix (believe me, there is a reason why I couldn’t use one of the numerous BLAS packages)
• Comparing real matrices for equality overload operator
• Comparing coefficients of two polynomials for solving ARIMA equations in time-series forecasting
• Calculating approximate correlation coefficients for groups of variables
• Coding Quasi-Newton methods (specially for solving box-constrained problems)

So, I was quite pleased to see this topic covered in a recent post by Peter Vogel in the Visual Studio magazine. Comparing my code with Peter’s code got me thinking a bit, and hence this post.

Absolute and Relative Comparison
For starters, I have been using absolute comparison with constant epsilon value (1E-15), and it has been working pretty well. The code is simple, and looks like below:

public static bool AreEqual(double a, double b, double EPS)
{
     if ((a < 0 && b > 0) || (a > 0 && b < 0))
         return false;
     else
         return (Math.Abs(a - b) < EPS);
}

Peter, however, mentions: “Any fixed epsilon would likely be too small when comparing large numbers, or too large when comparing small numbers.” That is indeed true, and I generally get by with passing separate epsilon value for other situations. The relative version of the method, from Peter’s post, looks like this:

public static bool AlmostEqual(double a, double b)
{
     if (a == b)
         return true;
     else
         return Math.Abs(a - b) < Math.Abs(a) / 281474976710656.0;
}

For an explanation about the constant, see the original post. As is obvious, this won’t work well with numbers close to zero. There are other schemes, where one calculates (a-b)/a, or (a-b)/b, or (a-b)/max(a,b) and compares with an epsilon.

Using Double.Epsilon
Note, however, that using Double.Epsilon available in .NET as the epsilon value is not a good idea in these comparisons. Double.Epsilon is only useful if one is subtracting values between 0 and 1 as it's the "smallest positive Double value greater than zero". Since double values aren't evenly spaced and their distance increases with their magnitude, one won't ever get something around Double.Epsilon if one is subtracting two arbitrary values.

Other Methods
Recently, I came across another interesting post which shows how to compare two floats (and by extension, doubles) using integers. If you are interested, definitely check this out. Another suggestion that has been floated in these discussions, is to use arbitrary precision arithmetic (APA), but in most applications, doing everything in APA would be really slow. An example of the use of APA is Microsoft Windows Calculator (the calc.exe program).

End Word
One sentiment that repeatedly seems to appear in posts related to this topic is that “the chosen method would really depend on what one would consider equal”. It is definitely application specific, and with enough spread in test cases, a wrong choice of method would show up in wrong result (or, so we hope !!).

References
Following are two really good references I have found on this topic:
[1] Jon Skeet’s coverage for floats and doubles and decimals
[2] Bruce Dawson’s coverage

Update (March 5th, 2017): Updated dead link.