Validity of Algorithm for Testing Two Floating Point Numbers

Question

This question is related to the epsilon- (or delta- if you prefer) test for floating point equality. But my question is not how to do it. Instead I have a related algorithm for testing equality, and I would like feedback as to what might be wrong with it.

The idea is to take the quotient of two floating point numbers and compare it to one. This eliminates the difficulty of choosing a value for epsilon. I have tested it extensively and am happy with the results. Here is a sample implementation in Java.

public class DoubleEquals
{
    public static final double  EPSILON = 1e-14;
    
    public static boolean equals( double param1, double param2 )
    {
        // Accounts for 0, +/-INFINITY;
        // if both values are NaN the result will be false
        boolean result  = param1 == param2;
        if ( !result )
        {
            double quot = param1 / param2;
            result = quot > 0 && (1 - quot) < EPSILON;
        }
        
        return result;
    }
}
```

Answer 1

There is one method to compare floating point numbers for equality, which is both very simple and correct: You use the equality (==) operator.

There is another method to compare whether floating point numbers are identical, which unlike the equality operator would find that -0 and +0 are not the same, and that NaNs with the same bit pattern are the same: Use memcmp. (Don't do this if your compiler stores 80 bit long double into 128 bits).

What you are talking about is the question: "Are these two numbers so close together that their difference could be due to rounding errors alone", and another question would be "Are these two numbers so close together that we don't care that they are different".

Swift has decided to put an operator for the latter into its standard library. This considers floating numbers with an n bit mantissa "as good as equal" if the difference is at most the last n/2 bits.

So first don't call your function "equals", because that is a lie. Call it "almostEqual" or something like that. Then make sure that it returns true without failure whenever x == y, that almostEqual (x, y) == almostEqual (y, x) for all pairs x, y, and that it returns the same result if you scale x, y both by the same power of two (unless this produces overflow or underflow).

Be aware that you cannot guarantee that almostEqual(x,y) and almostEqual(y,z) implies almostEqual(x,z). This also implies that you cannot make it compatible with any hash function.

Answer 2

That solution would be improved by ditching the fixed epsilon in favor of 1 or 2 ULPs. See the Java docs for:

public static double ulp(double d)

A second suggestion: implement a single precision version and test with double to convince yourself the algorithm is valid.