for loop debug in java - value overflow

Question

I'm working out this problem from Programming in Java book-site (for practice, not a HW.. Q15 in http://introcs.cs.princeton.edu/java/13flow/) :

Find the sum for the harmonic series 1/1 + 1/4 + 1/9 + 1/16 + ... + 1/N2 . There are 4 variants of for loops, some of them are supposed to give the right answer. My expected answers are in comments, and the actual results are below.

public class OneThreeExFifteen {
    public static void main(String[] args) { 
        int N = 1000000;
        double s1=0 , s2 = 0, s3 = 0, s4=0;

        for (int i = 1; i <= N ; i++ )
            s1 = s1 + 1 / ( i * i );        // Expected  s1 = 1 
        for (int i = 1 ; i <= N ; i++ ) 
            s2 = s2 + 1.0 / i * i;          // Expected  s2 = 1000000 
        for (int i = 1 ; i <= N ; i++) 
            s3 = s3 + 1.0 / (i * i) ;       // Correctly computes the series sum 
        for (int i = 1; i <= N ; i++ ) 
            s4 = s4 + 1 / (1.0 * i * i) ;   // Correctly computes the serires sum

        System.out.println("for loop 1" + s1);
        System.out.println("for loop 2" +s2);
        System.out.println("for loop 3" +s3);
        System.out.println("for loop 4" +s4);


    }
}

RESULT:

for loop 1       (  I get a Divide by 0  error - had to comment out this loop) 
for loop 2   1000000.0 
for loop 3   Infinity 
for loop 4   1.64493306684877

QUESTION - Why do I get

a) Divide by zero error?

b) Infinity result in case of for loop 3 ?

Answer 1

Sure, as another has already stated, you have performed integer division with the code 1 / ( i * i ) in multiple places. In Java, an int divided by an int must remain an int, so 1 divided by a larger number yields 0. But you aren't dividing by zero for that reason. That just makes you add zero, perfectly un-exceptional.

You are looping for i from 0 to 1000000 (1 million). Before you get too far, i is 65536 (2 to the 16th power). When this iteration occurs, i * i overflows (the "real" result is 2^32) and you get 0. This result is causing divide by zero in the first loop.

Demonstration program:

public static void main (String args[]) throws IOException
{
  int i = 1 << 16;  // 2^16, or 65536
  System.out.println(i);
  int j = i * i;
  System.out.println(j);
}

Output:

65536
0

The 3rd for loop is very similar, except that floating point division yields Infinity (a legal floating point value) instead of a divide by zero error.

The second and fourth for loops correctly promote the multiplication to double before the operation, so no overflow occurs. But the second for loop is missing its parentheses, so 1 is added each time. The fourth for loop correctly computes the sum.

Answer 2

System.out.println(65536*65536);

This will output 0.

I think this explains your problem for division by 0. You're getting an integer overflow. The integer can only hold numbers up to a certain point.

However as stated elsewhere integer division is hurting you a lot. Even if you didn't get division by 0, your answers would be wrong because of integer division.

Answer 3

You're suffering from integer division here:

s1 = s1 + 1 / ( i * i );

i is an int, and every number without a suffix is implicitly int, so you're dividing 1/1, which results in 1, luckily.

Things happen when i increases though - if it's greater than 1, you're going to get 0 for every result until the end of the loop.

Something unusual happens in my debugger when figuring this out - the division by zero occurs when the number is 65536 - you're getting an overflow on 65536² - which is 2³² - which results in the int value becoming 0.

The second loop:

s2 = s2 + 1.0 / i * i;

You're getting burned by operator precedence. Division and multiplication have higher precedence than addition, so what this is actually doing is:

s2 = s2 + ((1.0 / i) * i);

You divide correctly, but your operator precedence is all wrong.

The third loop:

s3 = s3 + 1.0 / (i * i) ;

This is the same issue as above, but since you're in a floating-point context, anything divided by 0 results in a signed Infinity.