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;
            }
        }
    }
}

have you tried just running addFloats((float) Math.pow(2.0, 25.0));? — RAZ_Muh_Taz, Jan 12 '17 at 16:57
Why is your parameter a `Float`? Boxing isn't needed here and it will be unboxed every comparison (unless that's optimized somehow) — Salem, Jan 12 '17 at 16:59
http://stackoverflow.com/questions/12596695/why-does-a-float-variable-stop-incrementing-at-16777216-in-c — bsiamionau, Jan 12 '17 at 17:12
http://stackoverflow.com/questions/5039165/max-value-can-stored-in-java-float-with-two-digit-precision-2-digit-accuracy helped me understand why — RAZ_Muh_Taz, Jan 12 '17 at 17:19

score 16 · Accepted Answer · edited May 23 '17 at 12:17

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

In other words, the second one doesn't just take longer -- it's an infinite loop! — yshavit, Jan 12 '17 at 18:06
When you are in the domain from 2^24 to 2^25 where the representable `float`s are exactly the even integers, when you do `f += 1.0f;`, the exact mathematical result would be an odd integer. Since this is exactly midway between the two nearest representable numbers, most implementation will pick the [doubly even](https://en.wikipedia.org/wiki/Singly_and_doubly_even) one (i.e. the one divisible by four). If that is the case `16777216.0f + 1.0f` would be `16777216.0f` (no increment), while `16777218.0f + 1.0f` would be `16777220.0f` (actual increment is +2). — Jeppe Stig Nielsen, Jan 13 '17 at 15:01

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

1 Answers1