C# float infinite loop

Question

The following code in C# (.Net 3.5 SP1) is an infinite loop on my machine:

for (float i = 0; i < float.MaxValue; i++) ;

It reached the number 16777216.0 and 16777216.0 + 1 is evaluates to 16777216.0. Yet at this point: i + 1 != i.

This is some craziness.

I realize there is some inaccuracy in how floating point numbers are stored. And I've read that whole numbers greater 2^24 than cannot be properly stored as a float.

Still the code above, should be valid in C# even if the number cannot be properly represented.

Why does it not work?

You can get the same to happen for double but it takes a very long time. 9007199254740992.0 is the limit for double.

Answer 1

Right, so the issue is that in order to add one to the float, it would have to become

16777217.0

It just so happens that this is at a boundary for the radix and cannot be represented exactly as a float. (The next highest value available is 16777218.0)

So, it rounds to the nearest representable float

16777216.0

Let me put it this way:

Since you have a floating amount of precision, you have to increment up by a higher-and-higher number.

EDIT:

Ok, this is a little bit difficult to explain, but try this:

float f = float.MaxValue;
f -= 1.0f;
Debug.Assert(f == float.MaxValue);

This will run just fine, because at that value, in order to represent a difference of 1.0f, you would need over 128 bits of precision. A float has only 32 bits.

EDIT2

By my calculations, at least 128 binary digits unsigned would be necessary.

log(3.40282347E+38) * log(10) / log(2) = 128

As a solution to your problem, you could loop through two 128 bit numbers. However, this will take at least a decade to complete.

Answer 2

Imagine for example that a floating point number is represented by up to 2 significant decimal digits, plus an exponent: in that case, you could count from 0 to 99 exactly. The next would be 100, but because you can only have 2 significant digits that would be stored as "1.0 times 10 to the power of 2". Adding one to that would be ... what?

At best, it would be 101 as an intermediate result, which would actually be stored (via a rounding error which discards the insignificant 3rd digit) as "1.0 times 10 to the power of 2" again.

Answer 3

To understand what's going wrong you're going to have to read the IEEE standard on floating point

Let's examine the structure of a floating point number for a second:

A floating point number is broken into two parts (ok 3, but ignore the sign bit for a second).

You have a exponent and a mantissa. Like so:

smmmmmmmmeeeeeee

Note: that is not acurate to the number of bits, but it gives you a general idea of what's happening.

To figure out what number you have we do the following calculation:

mmmmmm * 2^(eeeeee) * (-1)^s

So what is float.MaxValue going to be? Well you're going to have the largest possible mantissa and the largest possible exponent. Let's pretend this looks something like:

01111111111111111

in actuality we define NAN and +-INF and a couple other conventions, but ignore them for a second because they're not relevant to your question.

So, what happens when you have 9.9999*2^99 + 1? Well, you do not have enough significant figures to add 1. As a result it gets rounded down to the same number. In the case of single floating point precision the point at which +1 starts to get rounded down happens to be 16777216.0

Answer 4

It has nothing to do with overflow, or being near the max value. The float value for 16777216.0 has a binary representation of 16777216. You then increment it by 1, so it should be 16777217.0, except that the binary representation of 16777217.0 is 16777216!!! So it doesn't actually get incremented or at least the increment doesn't do what you expect.

Here is a class written by Jon Skeet that illustrates this:

DoubleConverter.cs

Try this code with it:

double d1 = 16777217.0;
Console.WriteLine(DoubleConverter.ToExactString(d1));

float f1 = 16777216.0f;
Console.WriteLine(DoubleConverter.ToExactString(f1));

float f2 = 16777217.0f;
Console.WriteLine(DoubleConverter.ToExactString(f2));

Notice how the internal representation of 16777216.0 is the same 16777217.0!!

Answer 5

The iteration when i approaches float.MaxValue has i just below this value. The next iteration adds to i, but it can't hold a number bigger than float.MaxValue. Thus it holds a value much smaller, and begins the loop again.