Why does this floating-point loop terminate at 1,000,000?

Question

The answer to this sample homework problem is "1,000,000", but I do not understand why:

What is the output of the following code?

int main(void) {
  float k = 1;
  while (k != k + 1) {
    k = k + 1;
  }
  printf(“%g”, k); // %g means output a floating point variable in decimal
}

If the program runs indefinitely but produces no output, write INFINITE LOOP as the answer to the question. All of the programs compile and run. They may or may not contain serious errors, however. You should assume that int is four bytes. You should assume that float has the equivalent of six decimal digits of precision. You may round your answer off to the nearest power of 10 (e.g., you can say 1,000 instead of 2¹⁰ (i.e., 1024)).

I do not understand why the loop would ever terminate.

Answer 1

It doesn't run forever for the simple reason that floating point numbers are not perfect.

At some point, k will become big enough so that adding 1 to it will have no effect.

At that point, k will be equal to k+1 and your loop will exit.

Floating point numbers can be differentiated by a single unit only when they're in a certain range.

As an example, let's say you have an integer type with 3 decimal digits of precision for a positive integer and a single-decimal-digit exponent.

With this, you can represent the numbers 0 through 999 perfectly as 000x10⁰ through 999x10⁰ (since 10⁰ is 1):

What happens when you want to represent 1000? You need to use 100x10¹. This is still represented perfectly.

However, there is no accurate way to represent 1001 with this scheme, the next number you can represent is 101x10¹ which is 1010.

So, when you add 1 to 1000, you'll get the closest match which is 1000.