Why does counting to 2^24 execute quickly, but counting to 2^25 take much longer?

Question

I was fiddling around making infinite loops to test some other code/my understanding, and came across this strange behaviour. In the program below, counting from 0 to 2^24 takes <100ms on my machine, but counting to 2^25 takes orders of magnitude more time (at time of writing, it's still executing).

Why is this the case?

This was under Java 1.8.0_101, on a 64-bit copy of Windows 10.

TestClass.java

public class TestClass {
    public static void main(String[] args) {
        addFloats((float) Math.pow(2.0, 24.0));
        addFloats((float) Math.pow(2.0, 25.0));
    }

    private static void addFloats(float number) {
        float f = 0.0f;
        long startTime = System.currentTimeMillis();

        while(true) {
            f += 1.0f;
            if (f >= number) {
                System.out.println(f);
                System.out.println(number + " took " + (System.currentTimeMillis() - startTime) + " msecs");
                break;
            }
        }
    }
}

Answer 1

This is because floats have a minimum precision that can be represented, which decreased as the float's value becomes larger. Somewhere between 2^24 and 2^25, adding one is no longer enough to change the value to the next largest representable number. At that point, every time through the loop, f just keeps the same value, since f += 1.0f no longer changes it.

If you change your loop to this:

while(true) {
    float newF = f + 1.0f;
    if(newF == f) System.out.println(newF);
    f += 1.0f;
    if (f >= number) {
        System.out.println(f);
        System.out.println(number + " took " + (System.currentTimeMillis() - startTime) + " msecs");
        break;
    }
}

You can see this happening. It seems as though it stops increasing as soon as f reaches 2^24.

The output of the above code will be an endless number of "1.6777216E7" if you run it with 2^25.

You can test this value by using the Math.nextAfter function, which tells you the next representable value. If you try running this code:

float value = (float)Math.pow(2.0, 24.0);
System.out.println(Math.nextAfter(value, Float.MAX_VALUE) - value);

you can see that the next representable value after 2^24 is 2^24 + 2.

For an excellent breakdown of why this happens, and why it starts mattering where it does, see this answer