Using "double" as counter variables in loops

Question

In a book I am currently reading, there is this excerpt:

You can also use a floating-point value as a loop counter. Here's an example of a for loop with this kind of counter:

double a(0.3), b(2.5);
for(double x = 0.0; x <= 2.0; x += 0.25)
    cout << "\n\tx = " << x << "\ta*x + b = " << a*x + b;

This code fragment calculates the value of a*x+b for values of x from 0.0 to 2.0, in steps of 0.25; however, you need to take care when using a floating-point counter in a loop. Many decimal values cannot be represented exactly in binary floating-point form, so discrepancies can build up with cumulative values. This means that you should not code a for loop such that ending the loop depends on a floating-point loop counter reaching a precise value. For example, the following poorly-designed loop never ends:

for(double x = 0.0 ; x != 1.0 ; x += 0.2)
    cout << x;

The intention with this loop is to output the value of x as it varies from 0.0 to 1.0; however, 0.2 has no exact representation as a binary floating-point value, so the value of x is never exactly 1. Thus, the second loop control expression is always false, and the loop continues indefinitely.

Can someone please explain how the first code block runs while the second doesn't?

Answer 1

The first one will eventually terminate, even if x doesn't reach exactly 2.0... because it'll end up being greater than 2.0, and thus break out.

The second one would have to make x hit exactly 1.0 in order to break.

It's unfortunate that the first example uses a step of 0.25, which is exactly representable in binary floating point - it would have been smarter to make both examples use 0.2 as the step size. (0.2 isn't exactly representable in binary floating point.)

Answer 2

The first block uses a less-than-or-equal condition (<=).

Even with floating-point inaccuracy, that will eventually be false.

Answer 3

This is an example of a broader issue - when comparing doubles, you often need to check for equality within some acceptable tolerance rather than exact equality.

In some cases, typically checking for an unchanged default value, equality is fine:

double x(0.0); 
// do some work that may or may not set up x

if (x != 0.0) {   
    // do more work 
}

In general though, checking versus an expected value cannot be done that way - you would need something like:

double x(0.0); 
double target(10000.0);
double tolerance(0.000001);
// do some work that may or may not set up x to an expected value

if (fabs(target - x) < tolerance) {   
    // do more work 
}

Answer 4

Floating point numbers are represented internally as a binary number, almost always in IEEE format You can see how numbers are represented here:

http://babbage.cs.qc.edu/IEEE-754/

For instance, 0.25 in binary is 0.01_b and is represented as +1.00000000000000000000000 * 2^-2.

This is stored internally with 1 bit for the sign, eight bits for the exponent (representing a value between -127 and +128, and 23 bits for the value (the leading 1. is not stored). In fact, the bits are:

[0][01111101][00000000000000000000000]

Whereas 0.2 in binary has no exact representation, just like 1/3 has no exact representation in decimal.

Here the problem is that just as 1/2 can be represented exactly in decimal format as 0.5, but 1/3 can only be approximated to 0.3333333333, 0.25 can be represented exactly as a binary fraction, but 0.2 cannot. In binary it is 0.0010011001100110011001100...._b where the last four digits repeat.

To be stored on a computer it is roudned to 0.0010011001100110011001101_b. Which is really, really close, so if you're calculating coordinates or anything else where absolute values matter, it's fine.

Unfortunately, if you add that value to itself five times, you will get 1.00000000000000000000001_b. (Or, if you had rounded 0.2 down to 0.0010011001100110011001100_b instead, you would get 0.11111111111111111111100_b)

Either way, if your loop condition is 1.00000000000000000000001_b==1.00000000000000000000000_b it will not terminate. If you use <= instead, it's possible it will run one extra time if the value is just under the last value, but it will stop.

It would be possible to make a format that can accurately represent small decimal values (like any value with only two decimal places). They are used in financial calculations, etc. But normal floating point values do work like that: they trade the ability to represent some small "easy" numbers like 0.2 for the ability to represent a wide range in a consistent fashion.

It's common to avoid using a float as a loop counter for that exact reason, common solutions would be:

• If one extra iteration doesn't matter, use <=
• If it does matter, make the condition <=1.0001 instead, or some other value smaller than your increment, so off-by-0.0000000000000000000001 errors don't matter
• Use an integer and divide it by something during the loop
• Use a class specially made to represent fractional values exactly

It would be possible for a compiler to optimise a float "=" loop to turn it into what you mean to happen, but I don't know if that's permitted by the standard or ever happens in practice.

Answer 5

There are multiple issues with the example, and two things are different between the cases.

• A comparison involving floating point equality requires expert knowledge of the domain, so it's safer to use < or > for loop controls.

• The loop increment 0.25 actually does have an exact representation

• The loop increment 0.2 does not have an exact representation

• Consequently, it's possible to exactly check for the sum of many 0.25 (or 1.0) increments but it isn't possible to exactly match even a single 0.2 increment.

A general rule is often cited: don't make equality comparisons of floating point numbers. While this is good general advice, when dealing with integers or integers plus fractions composed of ½ + ¼ ... you can expect exact representations.

And you asked why? The short answer is: because fractions are represented as ½ + ¼ ..., most decimal numbers don't have exact representations since they cannot be factored into powers of two. This means the FP internal representations are long strings of bits that will round to an expected value for output but not actually be exactly that value.

Answer 6

General practice is that that you do not compare two floating point numbers, i.e.:

// using System.Diagnostics;

double a = 0.2; a *= 5.0;
double b = 1.0;
Debug.Assert(a == b);

Because of the imprecision of floating point numbers, a might not exactly be equal to b. To compare for equality you might compare the difference of two numbers with a tolerance value:

Debug.Assert(Math.Abs(a - b) < 0.0001);