64
float a = 0;
while (true)
{
    a++;
    if (a > 16777216)
        break; // Will never break... a stops at 16777216
}

Can anyone explain this to me why a float value stops incrementing at 16777216 in this code?

Edit:

Or even more simple:

float a = 16777217; // a becomes 16777216
user
  • 5,335
  • 7
  • 47
  • 63
Jan
  • 791
  • 1
  • 5
  • 8
  • http://stackoverflow.com/questions/3448777/how-to-represent-0-1-in-floating-point-arithmetic-and-decimal – horgh Sep 26 '12 at 07:53
  • http://stackoverflow.com/questions/6275327/understanding-floating-point-representation-errors-whats-wrong-with-my-thinkin – horgh Sep 26 '12 at 07:54
  • 6
    If something like this is catching you out, I strongly advise you to read: What every computer scientist should know about floating point arithmetic. It explains how they're implemented in hardware and covers all the gotcha's you'll eventually run into. http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html – Dan Is Fiddling By Firelight Sep 26 '12 at 12:47

4 Answers4

71

Short roundup of IEEE-754 floating point numbers (32-bit) off the top of my head:

  • 1 bit sign (0 means positive number, 1 means negative number)
  • 8 bit exponent (with -127 bias, not important here)
  • 23 bits "mantissa"
  • With exceptions for the exponent values 0 and 255, you can calculate the value as: (sign ? -1 : +1) * 2^exponent * (1.0 + mantissa)
    • The mantissa bits represent binary digits after the decimal separator, e.g. 1001 0000 0000 0000 0000 000 = 2^-1 + 2^-4 = .5 + .0625 = .5625 and the value in front of the decimal separator is not stored but implicitly assumed as 1 (if exponent is 255, 0 is assumed but that's not important here), so for an exponent of 30, for instance, this mantissa example represents the value 1.5625

Now to your example:

16777216 is exactly 224, and would be represented as 32-bit float like so:

  • sign = 0 (positive number)
  • exponent = 24 (stored as 24+127=151=10010111)
  • mantissa = .0
  • As 32 bits floating-point representation: 0 10010111 00000000000000000000000
  • Therefore: Value = (+1) * 2^24 * (1.0 + .0) = 2^24 = 16777216

Now let's look at the number 16777217, or exactly 224+1:

  • sign and exponent are the same
  • mantissa would have to be exactly 2-24 so that (+1) * 2^24 * (1.0 + 2^-24) = 2^24 + 1 = 16777217
  • And here's the problem. The mantissa cannot have the value 2-24 because it only has 23 bits, so the number 16777217 just cannot be represented with the accuracy of 32-bit floating points numbers!
AndiDog
  • 68,631
  • 21
  • 159
  • 205
17

16777217 cannot be represented exactly with a float. The next highest number that a float can represent exactly is 16777218.

So, you try to increment the float value 16777216 to 16777217, which cannot be represented in a float.

Eric J.
  • 147,927
  • 63
  • 340
  • 553
13

When you look at that value in its binary representation, you'll see that it's a one and many zeroes, namely 1 0000 0000 0000 0000 0000 0000, or exactly 2^24. That means, at 16777216, the number has just grown by one digit.

As it's a floating point number, this can mean that the last digit at its end that is still stored (i.e. within its precision) is shifted to the left, as well.

Probably, what you're seeing is that the last digit of precision has just shifted to something bigger than one, so adding one doesn't make any difference any more.

O. R. Mapper
  • 20,083
  • 9
  • 69
  • 114
  • 3
    May I learn the reason for the -1? I'd gladly like to improve my answer. – O. R. Mapper Sep 26 '12 at 13:17
  • 1
    And even if I may not learn the reason for the first downvote, may I ask for a reason for the second one, please? – O. R. Mapper Jan 07 '15 at 13:10
  • `1000000000000000000000000` is a binary representation for `16777216` integer, but OP asks about a float (binary `01001011100000000000000000000000`). This answer is far from tackling OP's question, and perhaps even completely unrelated. Every power of 2 is written as `1` followed by zeroes, but not every power of two is the last number where OP's issue doesn't happen. Perhaps downvoters are right to say "this answer is not useful". – Markus von Broady Feb 03 '22 at 20:13
  • @MarkusvonBroady: If you look at those numbers, you'll recognize that `1000000000000000000000000` is precisely the mantissa part of your binary float representation `01001011100000000000000000000000`, plus the last digit that gets dropped due to a lack of precision in the float. As it is exactly that last digit that would change when adding `1` to the number, that change does not change the float number, leading to the phenomenon the OP was asking about. Which is exaclty what I explained in the answer. It is a mystery to me how you can consider the answer "perhaps even completely unrelated". – O. R. Mapper Feb 03 '22 at 21:27
  • The mantissa part is after 1+8 bits, it's all zeroes, without any `1`. You get the same mantissa for any power of 2. – Markus von Broady Feb 03 '22 at 21:54
4

Imagine this in decimal form. Suppose you had the number: 

1.000000 * 10^6

or 1,000,000. If all you had were six digits of accuracy, adding 0.5 to this number would yield

1.0000005 * 10^6

However, current thinking with fp rounding modes is to use "Round to Even," rather than "Round to Nearest." In this instance, every time you increment this value, it will round back down in the floating point unit back to 16,777,216, or 2^24. Singles in IEE 754 is represented as:

+/- exponent (1.) fraction

where the "1." is implied and the fraction is another 23 bits, all zeros, in this case. The extra binary 1 will spill into the guard digit, carry down to the rounding step, and be deleted each time, no matter how many times you increment it. The ulp or unit in the last place will always be zero. The last successful increment is from:

+2^23 * (+1.) 11111111111111111111111 -> +2^24 * (1.) 00000000000000000000000
Max
  • 121
  • 3
  • Maybe worth to note binary `1.11111111111111111111111` is decimal `1.9999998807907104`, and so 2^23 * 1.9999998807907104 = 8388608 * 1.9999998807907104 = 16777214.9999999995871232 – Markus von Broady Feb 03 '22 at 20:20