119

I ran cross this puzzler from an advanced programming course at a UK university exam.

Consider the following loop, in which i is, so far, undeclared:

while (i == i + 1) {}

Find the definition of i, that precedes this loop, such that the while loop continues for ever.

The next question, which asked the same question for this code snippet:

while (i != i) {}

was obvious to me. Of course in this other situation it is NaN but I am really stuck on the prior one. Does this have to do with overflow? What would cause such a loop to loop for ever in Java?

15
  • 3
    Any possibilities to override .equals() method? Since i is undeclared, we may use any class of what we want.
    – Geno Chen
    Nov 28, 2018 at 9:35
  • 7
    @Raedwald studying "unprofessional" code makes you more "professional", so... Anyway, it's a good question Nov 28, 2018 at 9:56
  • 12
    Fun fact, in C# this also works for nullable numeric types whose values are null, since null == null is true, and null + 1 is null. Nov 28, 2018 at 15:38
  • 4
    @EricDuminil: The situation is far worse than you imagine. In many languages, floating point arithmetic must be done in at least the 64 bits of precision specified by a double, which means that it can be done in higher precision at the whim of the compiler, and in practice this happens. I can point you at a dozen questions on this site from C# programmers who are wondering why 0.2 + 0.1 == 0.3 changes its value depending on compiler settings, the phase of the moon, and so on. Nov 28, 2018 at 23:38
  • 5
    @EricDuminil: The blame for this mess falls on Intel, who gave us a chip set that does higher-precision and faster floating point arithmetic if the numbers can be enregistered, which means that the results of a floating point computation can change their values depending on how well the register scheduler in the optimizer works today. Your choices as a language designer are then between repeatable computations and fast, precise computations, and the community that cares about floating point math will opt for the latter. Nov 28, 2018 at 23:41

4 Answers 4

142

First of all, since the while (i == i + 1) {} loop doesn't change the value of i, making this loop infinite is equivalent to choosing a value of i that satisfies i == i + 1.

There are many such values:

Let's start with the "exotic" ones:

double i = Double.POSITIVE_INFINITY;

or

double i =  Double.NEGATIVE_INFINITY;

The reason for these values satisfying i == i + 1 is stated in
JLS 15.18.2. Additive Operators (+ and -) for Numeric Types:

The sum of an infinity and a finite value is equal to the infinite operand.

This is not surprising, since adding a finite value to an infinite value should result in an infinite value.

That said, most of the values of i that satisfy i == i + 1 are simply large double (or float) values:

For example:

double i = Double.MAX_VALUE;

or

double i = 1000000000000000000.0;

or

float i = 1000000000000000000.0f;

The double and float types have limited precision, so if you take a large enough double or float value, adding 1 to it will result in the same value.

15
  • 10
    Or (double)(1L<<53) -- or float i = (float)(1<<24) Nov 28, 2018 at 9:43
  • 3
    @Ruslan: Any mathematician would disagree. Floating point numbers make very little sense. They are non-associative, non-reflexive (NaN != NaN), and not even substitutable (-0 == 0, but 1/0 != 1/-0). So most of the machinery of algebra is inapplicable.
    – Kevin
    Nov 28, 2018 at 16:35
  • 2
    @Kevin while floating-point numbers can't indeed make too much sense in general, the behavior of infinities (which is what is described in that sentence) was designed to make sense.
    – Ruslan
    Nov 28, 2018 at 16:38
  • 4
    @Kevin To be fair to floats, if you deal with infinities or undefined values you can't assume the properties you listed in algebra either.
    – Voo
    Nov 28, 2018 at 17:11
  • 2
    @Kevin: IMHO, floating-point maths could have made a lot more sense if they'd replaced the concepts of "positive and negative zero" sign positive, negative, and unsigned "infinitesimals" along with one "true zero", and made NaN equal to itself. True zero could behave as an additive identity in all cases, and something operations involving division by infinitesimals would lose their bias towards assuming the infinitesimals are positive.
    – supercat
    Nov 28, 2018 at 17:15
64

These puzzles are described in detail in the "Java Puzzlers: Traps, Pitfalls, and Corner Cases" book by Joshua Bloch and Neal Gafter.

double i = Double.POSITIVE_INFINITY;
while (i == i + 1) {}

or:

double i = 1.0e40;
while (i == i + 1) {}

both will result in an infinite loop, because 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 successor1.

A note about the second puzzle (for future readers):

double i = Double.NaN;
while (i != i) {}

also results in an infinite loop, because NaN is not equal to any floating-point value, including itself 2.


1 - Java Puzzlers: Traps, Pitfalls, and Corner Cases (chapter 4 - Loopy Puzzlers).

2 - JLS §15.21.1

0
1

double i = Double.POSITIVE_INFINITY;

0

Just an idea: what about booleans?

bool i = TRUE;

Isn't this a case where i + 1 == i?

4
  • depends on the language. Many languages automatically coerce booleans to ints when combined with an int. Others do as you suggest - coercing the int to a boolean. Nov 29, 2018 at 16:12
  • 8
    This question is a Java question, and your suggestion doesn't pass compilation in Java (which has no + operator that takes a boolean and an int as operands).
    – Eran
    Nov 30, 2018 at 9:05
  • @Eran: that's the whole idea of operator overloading. You can make Java booleans behave like C++ ones.
    – Dominique
    Nov 30, 2018 at 9:26
  • 4
    Except that Java doesn't support operator overloading, so you can't.
    – CupawnTae
    Dec 5, 2018 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.