Rule of thumb to test the equality of two doubles in C#?

Question

Let's say I have some code that does some floating point arithmetic and stores the values in doubles. Because some values can't be represented perfectly in binary, how do I test for equality to a reasonable degree of certainty?

How do I determine what "reasonable" means?

Can double.Epsilon be used in some way?

---

Update

Couple things. As @ho1 pointed out, the documentation for double.Epsilon points out that, when it comes to comparing two doubles for equality, you are probably going to want a value much greater than epsilon. Here is the relevant paragraph from the documentation:

Two apparently equivalent floating-point numbers might not compare equal because of differences in their least significant digits. For example, the C# expression, (double)1/3 == (double)0.33333, does not compare equal because the division operation on the left side has maximum precision while the constant on the right side is precise only to the specified digits. If you create a custom algorithm that determines whether two floating-point numbers can be considered equal, you must use a value that is greater than the Epsilon constant to establish the acceptable absolute margin of difference for the two values to be considered equal. (Typically, that margin of difference is many times greater than Epsilon.) -- http://msdn.microsoft.com/en-us/library/system.double.epsilon.aspx

...but the question is, how many times greater??

In case it would affect your answer, my particular situation involves geometry calculations (such as dot products and cross products using points and vectors). In some cases, you reach different conclusions based on whether A == B, A > B, or A < B, so I'm looking for a good rule of thumb for how to determine the size of the equivalence window.

Answer 1

Using double.Epsilon does NOT necessarily work. double.Epsilon gives the smallest representable value that is greater than zero. However, because of the way that floating point numbers are implemented, they have less precision the further away from zero they are, so checking for a difference of double.Epsilon could fail for two large numbers that are very close to each other.

Details: A base-2 floating point number is represented as a significand - a number between 1 and 2 - multiplied by two raised to some exponent. A double has 52 bits for the fractional portion of the significand plus 11 bits of precision for the exponent. If the exponent is a very large negative value and the significand is 0, then you get values close to double.Epsilon, but if your exponent is big enough, then even a very small difference in two significands' values will result in a value much larger than double.Epsilon.

For a full discussion on how to test two floating point numbers for equality, see "Comparing Floating Point Numbers, 2012 Edition", by Bruce Dawson. To summarize, there are three main methods of comparison:

Use an absolute difference

As in Joel Coehoorn's example, but be very careful to select a value that's of an appropriate magnitude, unlike Joel's example.

Use a relative difference

Something like the following:

if (Math.Abs(a - b) / b <= maxRelativeError)
{
    return true;
}

However, there are complications; you should divide by the larger of the two values, and this function performs poorly for values close to zero unless you also add a check for a maximum absolute difference. See the paper for details.

Using units of last place

Comparison using units of last place (ULPs) means checking the last portion of the significand. (The paper refers to this as "Comparing using integers.") This is a more complicated approach but is very robust. The paper provides source code in C; for C#, you could probably use BitConverter.DoubleToInt64Bits.

In response to your edit

"How many times greater?" This is really a question of your application domain, which is probably why the .NET Framework doesn't provide a default method, but I've had good luck using the ULPs comparison with a max ULPs difference of 4.

Answer 2

It depends a bit on what kind of values you're working with. If you're working with numbers where you only care about 2 decimal points it might be ok to just use 0.001. You might be able to use Epsilon sometimes, but normally I think not.

Edit: Removed reference to currency since it distracted from the point.

Quote from MSDN:

If you create a custom algorithm that determines whether two floating-point numbers can be considered equal, you must use a value that is greater than the Epsilon constant to establish the acceptable absolute margin of difference for the two values to be considered equal. (Typically, that margin of difference is many times greater than Epsilon.)

Answer 3

double d1 = GetRandomDouble();
double d2 = GetRandomDouble();

if (Math.Abs(d1 - d2) < double.Epsilon)
{
   // the doubles are equal
}

Note that in practice this code is equivalent to just d1 == d2, because epsilon is defined as the smallest possible positive value > 0. Thus you'll never have a value between 0 and epsilon, and if you have the kind of rounding/precision error that would cause problems with the == operator you'll see it here, too.

But what you can do is use the technique to define your own precision level — you're own epsilon. I would expect double.Equals() to have an overloaded for this technique, but the documentation is clear that one strangely does not exist. So let's make our own:

public static bool IsEqual(this double d1, double d2, unsigned int precisionFactor)
{
   return Math.Abs(d1 - d2) < precisionFactor * double.Epsilon;
}

Answer 4

so I'm looking for a good rule of thumb for how to determine the size of the equivalence window.

Unfortunately, there is no good rule of thumb here. It's entirely determined by the needs of your program. A toy physics simulation may prefer a very high epsilon so that collisions aren't missed. Meanwhile a statistics package would want a low epsilon to be more accurate. You'll just have to tune it to the needs of your app.

Answer 5

The question is, but many times greater??

How much larger depends on the inputs and on how many operations your performing. In addition to magnitude considerations, every operation increases your rounding error. If your doing many calculations on the numbers before comparing them it's more a matter of significant digits rather than machine accuracy.

Your window needs to be larger than the worst-case rounding error accumulated as a result of any calculations done. If it's smaller, there may be stray situations where your comparison fails.

Answer 6

Here is the implementation (comparing last bits of IEEE representation) mentioned in "Comparing Floating Point Numbers", by Bruce Dawsone, ported to C#.

One could argue that Float.NaN != Float.NaN. This code will treat all the special IEEE float value (NaN, Inf, etc) as equal. For Unit Testing, this is probably what you want. For real production code, you probably shouldn't compare NaN or Inf to anything - you should throw an Exception or something smart.

This is the same technique used by Google Test (gtest) for C++ as well.

Gtest uses a default value of 4 for the maxUlps.

    public static bool AlmostEqual2sComplement(float A, float B, int maxUlps)
    {
        // Make sure maxUlps is non-negative and small enough that the
        // default NAN won't compare as equal to anything.
        if (!(maxUlps > 0 && maxUlps < 4 * 1024 * 1024)) throw new Exception("maxUlps is invalid");

        Int32 aInt = BitConverter.ToInt32(BitConverter.GetBytes(A),0);
        // Make aInt lexicographically ordered as a twos-complement int
        if (aInt < 0)
            aInt = Int32.MinValue + (-aInt);
        // Make bInt lexicographically ordered as a twos-complement int
        Int32 bInt = BitConverter.ToInt32(BitConverter.GetBytes(B), 0);
        if (bInt < 0)
            bInt = Int32.MinValue + (-bInt);
        Int64 intDiff = Math.Abs(aInt - bInt);
        if (intDiff <= maxUlps)
            return true;
        return false;
    }
    public static bool AlmostEqual2sComplement(double A, double B, int maxUlps)
    {
        // Make sure maxUlps is non-negative and small enough that the
        // default NAN won't compare as equal to anything.
        if (!(maxUlps > 0 && maxUlps < 4 * 1024 * 1024)) throw new Exception("maxUlps is invalid");

        Int64 aInt = BitConverter.ToInt64(BitConverter.GetBytes(A), 0);
        // Make aInt lexicographically ordered as a twos-complement int
        if (aInt < 0)
            aInt = Int64.MinValue + (- aInt);
        // Make bInt lexicographically ordered as a twos-complement int
        Int64 bInt = BitConverter.ToInt64(BitConverter.GetBytes(B), 0);
        if (bInt < 0)
            bInt = Int64.MinValue + (- bInt);
        Int64 intDiff = Math.Abs(aInt - bInt);
        if (intDiff <= maxUlps)
            return true;
        return false;
    }