strange number of repetitions in for loop

Question

I wrote this little program to calculate pi.

While playing with the code and trying to find the most exact result, I found a point where my computer couldn't calalculate a result. It could do 33554430 repetitions within seconds, but if i increased the for loop to 33554431 it didn't output anything.

So is 33554430 a special number?

public class CalculatePi{
    public static void main(String[] args){
        float pi=0;
        int sign=1;
        for(float i=1; i <= 33554430; i+=2){
            pi += (sign*(1.0/i));
            sign*= -1;
        }
        pi *= 4;
        System.out.println(pi);
     }

}

Answer 1

You are getting and endless loop, because during the comparison i <= 33554431, the int value 33554431 is promoted to a float value which is "too precise" for float and will actually equal to 33554432. Then, when you try to increase the value by +2, the float just isn't precise enough to increment from the value 33554432. To illustrate my point:

float f = 33554432;
System.out.println(f); //33554432
f += 2;
System.out.println(f); //33554432

So the value f doesn't increase due to its precision limitation. If you'd increase it by, say 11, you'd get 33554444 (and not 33554443) as that is the closest number expressible with that precision.

So is 33554430 a special number?

Sort of, not 33554430 but rather 33554432. First "special number" for float is 16777217, which is the first positive integer that cannot be represented as a float (equals 16777216 as float). So, if you'd increment your i variable by 1, this is the number you'd get stuck on. Now, since you are incrementing by 2, the number you get stuck on is 16777216 * 2 = 33554432.

Answer 2

public class CalculatePi{
    public static void main(String[] args){
        float pi=0;
        int sign=1;
        for(float i=1; i <= 33554431; i+=2){
            pi += (sign*(1.0/i));
            sign*= -1;
        if( i > 33554410) System.out.println(i);
        }
        pi *= 4;
        System.out.println(pi);

        System.out.println((float)33554431);
        System.out.println((float)33554432);
        System.out.println((float)33554434);
     }

}

You compare float with int in for loop. When you convert 33554431 (it's int value) to float you get 3.3554432E7.

It's about accuracy, precision. When you run:

System.out.println((float)33554431);  // -> 3.3554432E7
System.out.println((float)33554432);  // -> 3.3554432E7
System.out.println((float)33554434);  // -> 3.3554432E7

All 3 prints 3.3554432E7, it means that when you increase float value of 33554432 by 2, you get 3.3554432E7, exactly this same value, and your loop runs forever.

Answer 3

This version works for both. It's the float loop variable causing problems:

public static void main(String[] args){
        float pi=0;
        int sign=1;
        for(int i=1; i <= 33554430; i+=2){
            pi += (sign*(1.0/(float)i));
            sign*= -1;
        }
        pi *= 4;
        System.out.println(pi);
    }

Probably this is due this issue:

The finite nonzero values of any floating-point value set can all be expressed in the form s · m · 2(e - N + 1), where s is +1 or -1, m is a positive integer less than 2N, and e is an integer between Emin = -(2K-1-2) and Emax = 2K-1-1, inclusive, and where N and K are parameters that depend on the value set.

Answer 4

Your loop increments by 2 each time.

2 * 33554430 = 67108860

2 ^ 26 = 67108864

Maybe Java stores floating point numbers in a 32bit system by using 26bits for the mantissa and 6 bits for the exponent?