CODEWITHSUNDEEP
javafloating-pointprecisionfloating-accuracy
k314159
k314159

Reputation: 11100

Floating-point equality unexpectedly working

We are often taught that floating-point numbers should not be compared for exact equality. However, the following function, which returns the Golden Ratio when passed any positive number, does in fact compare doubles for equality and to my surprise it seems to always work:

public static double f(double x) {
    double y;
    while ((y = 1 + 1 / x) != x)
        x = (x + y) / 2;
    return x;
}

@Test
void test() {
    assertEquals((1 + sqrt(5)) / 2, f(1.0));  // Passes!
}

I thought that maybe it works for some input arguments but not others. But even if I use JQwik's property testing, it still works!

@Property
void test2(@ForAll @Positive double x) {
    assertEquals((1 + sqrt(5)) / 2, f(x));  // Always passes!
}

Can anyone tell me why I never come across a situation where the two floating-point numbers are different by a very small amount?

Upvotes: 3

Views: 102

Answers (2)

chux
chux

Reputation: 153457

... and to my surprise it seems to always work:

Not always.

When I tried f(-1/1.6180339887498949), the x and y values oscillated between two floating point values that differed in the last few bits @Steve Summit. Thus an infinite loop.

x:-0.61803398874989490  y:-0.61803398874989468   // Decimal notation
x:-0x1.3c6ef372fe950p-1 y:-0x1.3c6ef372fe94ep-1  // Hex notation

x:-0.61803398874989479  y:-0.6180339887498949
x:-0x1.3c6ef372fe94fp-1 y:-0x1.3c6ef372fe950p-1

x:-0.61803398874989490  y:-0.61803398874989468
x:-0x1.3c6ef372fe950p-1 y:-0x1.3c6ef372fe94ep-1

f(some_starting_x) generally converges to render an x, such that 1 + 1 / x is x again and so meeting the stopping condition.

Better routines can prove that if x is reasonably close, the while loop will eventually get close to the desired answer, yet even then, an oscillation, as shown above is possible. Thus using an iteration limit or close enough test is needed. Usually the 2 oscillation values, when close, they are massaged (e.g. averaged) to form the best answer. If not close, the looping simply failed to find a stable answer.

Can anyone tell me why I never come across a situation where the two floating-point numbers are different by a very small amount?

Inadequate testing.

Morale of the story:

Do not rely on only floating point equality, except in select cases.
f() was not a select case and deserved additional stopping code.

Ref: Two x with math property: x = 1 + 1/x:

x1 = 1.6180339887498948482045868343656...
x2 = -0.61803398874989484820458683436564...

Note x1*x2 == -1. x1 is the Golden_ratio φ.

Upvotes: 1

Henry
Henry

Reputation: 43738

You were just lucky, in general you don't get exact equality. Try this for example:

public static void main(String[] args) {
    var s = 0.0;
    for (int i = 0; i < 10; i++) {
        s += 0.1;
    }
    System.out.println(s == 1.0);
}

In your concrete example one would have to do a careful analysis to prove that your iteration always converges to the floating point number closest to phi. If sqrt also returns the closest floating point number to the exact root we would get exact equality.

Upvotes: 2

Related Questions