1
$\begingroup$

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;
    }
}
```
$\endgroup$
3
  • 2
    $\begingroup$ Did you try with param1 = 1e+300 and param2 = 1e-300? Observe that also equals(param1,param2) == equals(param2,param1) is not always true, as it happens for the previous input. $\endgroup$ – plop Aug 16 '20 at 0:17
  • 1
    $\begingroup$ @plop Ooooo, nice catch. I added a test for quot < positive_infinity, but I'll need to give it more thought before I consider the issue resolved. I'll probably also have to test quot against NaN. Thanks for the help. $\endgroup$ – Jack Straub Aug 16 '20 at 0:55
  • $\begingroup$ (While coding is off-topic, this is a forum where a trailing code block needs a trailing newline to render properly. What is special about 1e-14? Have a look at MIN_NORMAL and MIN_VALUE.) $\endgroup$ – greybeard Aug 16 '20 at 1:43
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Very, very helpful, thank you. I've been struggling with what a hash function might look; it occurs to me that just returning 1 (or any constant value) would be valid, but the idea doesn't really please me. $\endgroup$ – Jack Straub Aug 17 '20 at 22:02
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Of course, using 2 ulps doesn't cover the case where one number is subnormal and the other is not... $\endgroup$ – Pseudonym Aug 17 '20 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.