Floating-point loop drift

Why this matters

Many loops count in decimal steps. A chart draws points every 0.1 seconds. A cooking timer steps through 0.25 cups. A money program moves through prices in steps of 0.05. A beginner often writes a loop like this one, which should run 11 times, from 0.0 to 1.0 in steps of 0.1:

for (double x = 0.0; x <= 1.0; x += 0.1) {
    // use x
}

That loop does not always do what it looks like. Sometimes the end value is never reached, and sometimes the loop runs one time too few. A loop with != as its test can run forever. The cause is how the computer stores decimal numbers. This lesson shows the cause with real output, then shows the fix: a loop controlled by a whole-number counter.

The lesson assumes you know for loops and the type double. A double is a number type in C++ that stores a value with about 15 to 17 significant digits. A significant digit is a digit that counts in the value, not a zero used only as a placeholder. Use double for real numbers, and use int for whole numbers.

Why 0.1 is not exact

A computer stores numbers in base 2, also called binary. Binary uses only the digits 0 and 1. Each digit in a whole number stands for a power of 2: 1, 2, 4, 8, 16 and so on. After the point, the places stand for halves, quarters, eighths and so on.

Some decimal fractions have a short binary form. One half is 0.1 in binary, one quarter is 0.01, and three quarters is 0.11. Others do not. One tenth is 0.0001100110011 and then the same block of digits repeats forever. A computer has room for only a fixed number of binary digits, so it must stop somewhere. The stored value is the closest number it can hold, which is a little above or a little below one tenth.

The first program prints the stored value of 0.1 with 20 digits after the point. It also adds 0.1 ten times, which should give exactly 1.0.

Output:

0.1 is stored as 0.10000000000000000555
ten additions of 0.1 give 0.99999999999999988898
sum == 1.0 is 0

The stored 0.1 is a little above one tenth. Each addition rounds its result to the nearest number the computer can hold, and the rounding errors add up. After ten additions the total is a little below 1.0, so the comparison sum == 1.0 is false. The 1 and 0 in the last line are how C++ prints a bool result, so sum == 1.0 printed 0, which means false.

This error is called drift. Drift is the slow build-up of small errors across many steps. Each step is tiny, but the steps add up.

Worked example 1: the loop that never stops

Here is a loop that should stop when x reaches 1.0. It uses !=, which means "not equal".

double x = 0.0;
while (x != 1.0) {
    x += 0.1;
}

The loop stops only if x is exactly 1.0 at some point. The values of x are not exact, so the test x != 1.0 never becomes false, and the loop has no end. The program below adds a cap of 12 steps. The cap is there only so the demo stops. A real loop like the one above has no cap.

Output:

step 0: x = 0
step 1: x = 0.10000000000000000555
step 2: x = 0.2000000000000000111
step 3: x = 0.30000000000000004441
step 4: x = 0.4000000000000000222
step 5: x = 0.5
step 6: x = 0.5999999999999999778
step 7: x = 0.69999999999999995559
step 8: x = 0.79999999999999993339
step 9: x = 0.89999999999999991118
step 10: x = 0.99999999999999988898
step 11: x = 1.0999999999999998668
stopped after 12 steps, x = 1.1999999999999999556

Look at step 10. The value is 0.99999999999999988898, which is close to 1.0 but not equal to it. The next value jumps to 1.0999999999999998668. The value 1.0 never appears. Step 5 shows x = 0.5. That value has a short binary form, so it is stored exactly, and a test with == can match it.

Worked example 2: an end value that is missed

Now use a <= test, which is the usual way to include an end value. The loop below counts from 20.0 to 21.0 in steps of 0.1. Someone might expect 11 values, because 21.0 is ten steps after 20.0.

Output:

t = 20
t = 20.100000000000001421
t = 20.200000000000002842
t = 20.300000000000004263
t = 20.400000000000005684
t = 20.500000000000007105
t = 20.600000000000008527
t = 20.700000000000009948
t = 20.800000000000011369
t = 20.90000000000001279
count: 10

The loop runs 10 times, not 11. The value after ten additions is 21.000000000000014211, which is slightly larger than 21.0. The test t <= 21.0 is then false, and the loop ends before it prints the end value. The printed values stop at 20.9, so the loop misses its end.

Changing <= to < does not fix this. The loop from 0.0 to 1.0 in steps of 0.1 still prints 11 values, and the last one is 0.99999999999999988898, not 1.0. A decimal step can land just above or just below the end, and the rounding of each step decides which. You cannot predict the count by reading the loop.

Worked example 3: an integer counter

The fix is to let an integer control the loop. The counter i is an exact whole number, so the loop always runs the same number of times. The decimal value is computed from i on each pass. The division i / 10.0 gives the closest stored number to the true quotient. That is the same stored number the literal 0.3 becomes, so comparisons with the decimal literal work.

Output:

i = 0  t = 20
i = 1  t = 20.100000000000001421
i = 2  t = 20.199999999999999289
i = 3  t = 20.300000000000000711
i = 4  t = 20.399999999999998579
i = 5  t = 20.5
i = 6  t = 20.600000000000001421
i = 7  t = 20.699999999999999289
i = 8  t = 20.800000000000000711
i = 9  t = 20.899999999999998579
i = 10  t = 21
3 / 10.0 == 0.3 is 1

This loop always runs 11 times, and the last value is exactly 21. The test i <= 10 is on integers, which are exact, so the loop can never miss its end. Each value is computed fresh from the counter, so an error in one value does not carry into the next.

Compare the two loops. In the drifting loop, t is changed by t += 0.1, and every change adds a new rounding error to the old one. In the integer loop, i is the only thing that changes, and the rounding happens once for each value. The number of steps is fixed by the integer limit, which you can read off the code.

Two details matter. The division must use 10.0, a double, not 10. With i / 10 in integer arithmetic, C++ would drop the fraction and give 0 for every value of i below 10. The second detail is the integer limit. When the step is 0.1 and the range is 0 to 1, the limit is i <= 10. When the step is 0.25 and the range is 0 to 1, the limit is i <= 4. Work the limit out from the range and the step before you write the loop.

A quick check tells you which steps can drift in a plain += loop. Write the step as a fraction in lowest terms. If the bottom number is a power of 2 (1, 2, 4, 8, 16 and so on), the step has an exact binary form. So 0.5, 0.25 and 0.125 are exact, while one tenth (0.1), one fifth (0.2) and one twentieth (0.05) are not. The integer counter works for every step, exact or not, so you do not need the check to write a correct loop. The check only tells you which loops would have shown the problem.

Harder case: a loop that stops at a closeness, not a count

Sometimes the number of steps is not known in advance. A loop may run until a value is close enough to a target, as in an approximation. The test cannot be ==. Instead, compare the distance to the target against a small tolerance, which is a small number that says how close is close enough.

Output:

steps: 10

The function std::fabs from the <cmath> header gives the size of a double with its sign removed, so the distance from -0.5 to 0 is 0.5. The distance from y to 1.0 is about 1 times 10 to the power of minus 16 after ten steps, which is well under the tolerance 1e-9, so the loop stops. The number 1e-9 means 1 times 10 to the power of minus 9, which is 0.000000001.

Use the tolerance form only when the count is unknown. When the count is known, use the integer counter, because it gives a fixed number of steps and does not depend on the size of the tolerance.

Common mistakes

Testing a decimal value with == or !=

A test like x == 0.3 depends on the exact stored value of each number. Often it is false when you expected true. The compiler can warn you about this if you ask it to. The -Wfloat-equal flag is not part of -Wall, so you must add it.

#include <iostream>
 
int main() {
    double x = 0.0;
    for (int i = 0; i < 10; ++i) {
        x += 0.1;
    }
    if (x == 1.0) {
        std::cout << "equal\n";
    }
}

Compile it with the flag:

g++ -std=c++20 -Wall -Wfloat-equal -o lf6 lf6.cpp

The compiler prints this warning:

lf6.cpp: In function ‘int main()’:
lf6.cpp:8:11: warning: comparing floating-point with ‘==’ or ‘!=’ is unsafe [-Wfloat-equal]
    8 |     if (x == 1.0) {
      |         ~~^~~~~~

The program compiles and runs, but it prints nothing, because x == 1.0 is false. The program fails without an error message. The warning is the only sign of the problem.

Printing with the default precision hides the drift

When you print a double without std::setprecision, C++ shows only about six significant digits. The drift is too small to appear, so the output looks exact.

Output:

1

The value is 0.99999999999999988898, but the output shows 1. A program that compares this value with == will still fail. Set the precision when you are checking a result, and remember that the printed value and the stored value can differ.

A loop with no end

A while loop that tests != against a decimal value may never end. The loop in the next program does not stop, because the value of y never equals 1.0. The program stops itself after one million calls, so you can see the result.

Output:

calls: 1000000  x = 100000

The value of x grows to about 100000 and never equals 1.0. Without the cap line, the program would not stop. The fix is the same as before: use a loop with an integer counter when the number of steps is known, or a tolerance when it is not.

Adding a step instead of computing the value

The loop t += 0.1 adds the step to the previous value, so each rounding error carries forward. Computing the value from the counter, as 20.0 + i / 10.0 does, starts over from an exact integer on each pass. The first worked example shows the carried error. The third worked example shows the counter version. Both use the same decimal steps, and the counter version ends at an exact 21.

Practice

Exercise 1: count the values

How many values does this loop print? List them.

int count = 0;
for (double x = 0.0; x < 0.5; x += 0.1) {
    ++count;
}

Show the answer

The loop prints 5 values: 0, 0.1, 0.2, 0.3 and 0.4. The value after five additions is 0.5, which is exact in binary, so the test x < 0.5 is false and the loop ends. The count is 5.

Exercise 2: rewrite with an integer counter

Rewrite exercise 1 so that an integer controls the loop. Each value must be computed as a decimal from the counter.

Show the answer

int count = 0;
for (int i = 0; i < 5; ++i) {
    double x = i / 10.0;
    ++count;
}

The loop runs for i from 0 to 4, so the count is 5, and each x is the closest stored value to 0.0, 0.1, 0.2, 0.3 and 0.4. The count comes straight from the integer limit, not from the drift.

Exercise 3: find the loop that never ends

The loop below should stop when x reaches 0.3. Explain why it does not stop, and rewrite it so that it stops after three steps.

for (double x = 0.0; x != 0.3; x += 0.1) {
    // ...
}

Show the answer

The values of x are 0, 0.1, 0.2 and then 0.30000000000000004, which is not equal to the stored 0.3, which is 0.29999999999999998890. The test x != 0.3 is always true, so the loop never ends. A fixed version uses an integer limit:

for (int i = 0; i < 3; ++i) {
    double x = i / 10.0;
    // ...
}

This loop runs for i equal to 0, 1 and 2, which gives the three values 0, 0.1 and 0.2.

Exercise 4: compare two decimal results

Write a check that prints 1 when 0.1 + 0.2 and 0.3 are equal to within 0.000000001, and 0 when they are not.

Show the answer

#include <cmath>
#include <iostream>
 
int main() {
    double a = 0.1 + 0.2;
    double b = 0.3;
    std::cout << (std::fabs(a - b) < 1e-9) << '\n';
}

The program prints 1. The direct test a == b would print 0, because the sum is 0.30000000000000004 and the literal is 0.29999999999999998890.

Exercise 5: count the quarter steps

Predict how many values this loop prints, then run it to check.

int count = 0;
for (double x = 0.0; x <= 1.0; x += 0.25) {
    ++count;
}

Show the answer

The count is 5: 0.0, 0.25, 0.5, 0.75 and 1.0. Every one of these is a sum of powers of one half, so each is exact in binary. The last value equals 1.0, and <= includes it. This loop is safe only because 0.25 has an exact binary form. The same code with 0.1 would not be safe.

Summary

• A decimal such as 0.1 has no exact binary form, so each stored value is a little off.
• Adding a decimal step many times makes the error grow, which is called drift.
• A loop test with == or != on a decimal value may never be true, and the loop may never end.
• Use an integer counter for the loop, and compute the decimal value from it with a division by 10.0.
• Use a tolerance such as std::fabs(a - b) < 1e-9 to compare decimal results. In a loop, use it only when the number of steps is not known in advance.
• Turn on -Wfloat-equal when you want the compiler to warn about == and != on decimal values.