Why does the floating point cycle end at 1,000,000?

Question

The answer to this trial home problem is "1,000,000", but I don't 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 does not exit, write INFINITE LOOP as the answer to the question. All programs are compiled and run. However, they may or may not contain serious errors. You should assume that int is four bytes. You should assume that float has the equivalent of six decimal digits of precision. You can round your answer to the nearest power of 10 (for example, you can say 1000 instead of 2 ¹⁰ (i.e. 1024)).

I do not understand why the cycle will be completed.

Answer 1

It does not work forever for the simple reason that floating point numbers are not perfect.

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

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

Floating point numbers can be differentiated by one block only if they are in a certain range.

As an example, suppose you have an integer type with 3 decimal digits of precision for a positive integer and a metric with one decimal digit.

In this case, you can perfectly represent numbers from 0 to 999 as 000x10 ⁰ through 999x10 ⁰ (since 10 ⁰ is 1):

What happens if you want to introduce 1000? You need to use 100x10 ¹ . It is still beautifully presented.

However, there is no exact way to represent 1001 with this diagram, the next number you can imagine is 101x10 ¹ which equals 1010.

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

Answer 2

The code uses the variable float .

As stated in the question, float has 6 digits of accuracy, which means that any digits after the sixth will be inaccurate. Therefore, as soon as you pass a million, the last digit will be inaccurate, so its increment may not have an effect.

Answer 3

The result of this program is not specified by the C standard, since the semantics of type float not specified. One likely result (what you get on a platform for which float arithmetic is evaluated in IEEE-754 single precision), 2^24 .

All integers less than 2^24 are accurately represented in the same precision, so the calculation will not stop at this point. The next representable single precision number after 2^24 , however, 2^24 + 2 . Since 2^24 + 1 is halfway between this number and 2^24 , in the rounding mode of the default IEEE-754, it is rounded to the last bit equal to zero, i.e. 2^24 .

Other likely answers include 2^53 and 2^64 . Other answers are possible. Infinity (floating point value) can occur on a platform for which, for example, the default rounding mode is rounded. As others have pointed out, an infinite loop is also possible on platforms that evaluate floating point expressions in a wider type (which is the source of all kinds of confusion for the programmer, but is allowed by the C standard).

Answer 4

Actually, on most C compilers this will work forever (an infinite loop), although the exact behavior is determined by the implementation.

The reason most compilers will give an infinite loop is because they evaluate all floating point expressions with double precision and only round the values ​​to floating point (single) precision when stored in a variable. Therefore, when the value of k reaches approximately 2 ^ 24, k == k + 1 will still be evaluated as false (since double can hold the value of k + 1 without rounding), but the purpose of k = k + 1 will be noop, since k + 1 must be rounded to insert into the float

change

gcc on x86 gets this infinite loop behavior. Interestingly, this is not the case on x64, as it uses sse commands that perform comparisons in exactly float.