Puzzle 28: Looper

This puzzle and the five that follow turn the tables on you. Instead of showing some code and asking what it does, they make you write the code, albeit in small amounts. These puzzles are called loopers. You will be shown a loop that looks as though it ought to terminate quickly, and it will be your job to come up with a variable declaration that makes it loop indefinitely, when placed immediately above the loop. For example, consider this for loop:

for (int i = start; i <= start + 1; i++) {

}

It looks as though it should run for only two iterations, but it can be made to loop indefinitely by taking advantage of the overflow behavior illustrated in Puzzle 26. The following declaration does the trick:

int start = Integer.MAX_VALUE - 1;

Now it's your turn. What declaration turns this loop into an infinite loop?

while (i == i + 1) {

}

Solution 28: Looper

Looking at the while loop, it really seems as though it ought to terminate immediately. A number is never equal to itself plus 1, right? Well, what if the number is infinity? Java mandates the use of IEEE 754 floating-point arithmetic [IEEE-754], which lets you represent infinity as a double or float. As we learned in school, infinity plus 1 is still infinity. If i is initialized to infinity before the loop starts, the termination test (i == i + 1) evaluates to true, and the loop never terminates.

You can initialize i with any floating-point arithmetic expression that evaluates to infinity; for example:

double i = 1.0 / 0.0;

Better yet, you can take advantage of a constant that is provided for you by the standard libraries:

double i = Double.POSITIVE_INFINITY;

In fact, you don't have to initialize i to infinity to make the loop spin forever. Any sufficiently large floating-point value will do; for example:

double i = 1.0e40;

This works because the larger a floating-point value, the larger the distance between the value and its successor. This distribution of floating-point values is a consequence of their representation with a fixed number of significant bits. Adding 1 to a floating-point value that is sufficiently large will not change the value, because it doesn't "bridge the gap" to its successor.

Floating-point operations return the floating-point value that is closest to their exact mathematical result. Once the distance between adjacent floating-point values is greater than 2, adding 1 to a floating-point value will have no effect, because the half-way point between values won't be reached. For the float type, the least magnitude beyond which adding 1 will have no effect is 2²⁵, or 33,554,432; for the double type, it is 2⁵⁴, or approximately 1.8 x 10¹⁶.

The distance between adjacent floating-point values is called an ulp, which is an acronym for unit in the last place. In release 5.0, the Math.ulp method was introduced to calculate the ulp of a float or double value.

In summary, it is possible to represent infinity as a double or a float. Most people find this somewhat surprising the first time they hear of it, perhaps because you can't represent infinity by using any of the integral types. Second, adding a small floating-point value to a large one will not change the large value. This too may be counterintuitive, as it isn't true for the real numbers. It is worth remembering that binary floating-point arithmetic is only an approximation to real arithmetic.