To debug a loop in java - value overflow

Question

I am developing this problem from programming on a Java site (for practice, not for HW .. Q15 at 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 options for loops, some of which should give the correct answer. My expected answers are given in the comments, and the actual results are given 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) Does infinity lead to the case for cycle 3?

Answer 1

Of course, as mentioned elsewhere, you performed integer division with the code 1 / ( i * i ) in several places. In Java, an int symbol divided by int must remain int , so 1 divided by a larger number gives 0 . But for this reason you do not divide by zero. It just makes you add zero, not at all exceptional.

You are looping for i from 0 to 1000000 (1 million). Before going too far, i will be 65536 ( 2 to 16th power). When this iteration happens, i * i overflows (the "real" result is 2^32 ), and you get 0 . This result causes division by zero in the first cycle.

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 third for loop is very similar, except that floating point division gives Infinity (legal floating point value) instead of division by zero error.

The second and fourth for loops correctly support double multiplication before the operation, so overflow does not occur. But the second for loop does not have its parentheses, so 1 added every time. The fourth for loop correctly calculates the sum.

Answer 2

Here you are suffering from integer division:

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

i is int , and every number without a suffix is ​​implicitly int , so you divide 1/1, which, fortunately, leads to 1.

Things happen when i increases, although if it is greater than 1, you will get 0 for each result until the end of the loop.

Something unusual happens in my debugger when calculating this - division by zero occurs when the number 65536 - you get an overflow of 65536 ² - which is 2 ³² which causes the int value to become 0.

Second cycle:

 s2 = s2 + 1.0 / i * i; 

You are burned by operator priority. Separation and multiplication have a higher priority than adding, so this is actually:

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

You divide correctly, but the priority of your operator is incorrect.

Third cycle:

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

This is the same problem as above, but since you are in a floating-point context , anything divisible by 0 results in a signed Infinity .

Answer 3

System.out.println(65536*65536);

This will lead to output 0.

I think this explains your problem for dividing by 0. You get integer overflow . An integer can only contain numbers up to a certain point.

However, as indicated elsewhere, integer division is bad for you. Even if you did not get the division by 0, your answers would be incorrect due to integer division.

Answer 4

The first is just an overflow error. One simple way to prove this is to show the self before the division (it will be 65536, or 2 ^ 16). The limit for int is 2 ^ 32, and integers move around when they pass their maximum value, so 2 ^ 32 = 0

(i * i) = (2 ^ 16 * 2 ^ 16) = 2 ^ 32 = 0