Floating-point numbers

A floating-point number, such as double in C++, stores a number with a fraction (3.5, 0.1, 66.6667) using a fixed number of digits, about 15–16. Most fractions are stored only approximately, so solutions compare doubles with a small tolerance and print them with a fixed number of digits after the point. If every value in the problem is an integer, keep it in an integer type, which is exact.

Explanation

A calculator keeps 4 digits after the point. Divide 1 by 3: 1/3 has no exact form with 4 digits, so the calculator keeps the nearest, 0.3333. Multiply that by 3 and it shows 0.9999, not 1.

Fig. 1. A calculator that keeps 4 digits can't store 1/3 exactly, so the result is 0.9999 instead of 1.

A double does the same, but it keeps about 15–16 significant digits, counted from the first non-zero digit. For 0.1234 that leaves about 15 digits after the point; for 123456789.5 only about 7. A double also stores numbers in binary. In binary, only fractions built from halves, quarters, eighths and so on are exact, such as 0.5, 0.25 and 0.375. 0.1 is not one of them, just as 1/3 has no exact decimal form, so a double keeps the nearest number it can store: 0.1000000000000000055511151. Every operation on doubles rounds its result the same way, so tiny errors of about 10^{-16} of the value build up.

Fig. 2. Each addition rounds. The errors go up and down, and after ten steps x is just below 1.

A loop for (double x = 0; x != 1.0; x += 0.1) therefore never stops: x steps over 1.0 without being equal to it. Count with an integer i and compute x = i * 0.1 instead.

Take two variables double a = 0.1, b = 0.2; and test a + b == 0.3. The test is false, yet cout << a + b prints 0.3, so it looks as if == is broken. Printing 17 digits with cout << setprecision(17) shows the difference: a + b is 0.30000000000000004, and 0.3 itself is stored as 0.29999999999999999.

Fig. 3. The blue tick is the nearest double to 0.3; 0.1 + 0.2 lands on the red tick.

No double lies between the two ticks, and the gap between these neighbours is 5.55 \cdot 10^{-17}. 0.1 and 0.2 are each already a little off, so their sum lands one gap too far.

Instead of ==, test whether two doubles are closer than a tolerance called EPS: fabs(a + b - 0.3) < 1e-9 is true, where fabs is the absolute value of a double. A rule of thumb is EPS = 1e-9 for values up to about 10^4: each operation is off by about 10^{-16} of the value, about 10^{-12} at 10^4, which leaves room for many operations. EPS must be larger than the error that builds up, and smaller than any real difference the problem can have: inputs with 3 digits after the point differ by at least 10^{-3}.

Every a within EPS of b counts as equal to b. So a is less than b only below that band, a < b - EPS, and greater only above it, a > b + EPS.

Fig. 4. The band is 2·EPS wide; the figure is not to scale.

By default, cout prints 6 significant digits: 200.0 / 3 prints 66.6667, and 1234567.0 prints 1.23457e+06, because 6 digits don't hold its whole part. Problems ask for a fixed number of digits after the point. With fixed in front, setprecision(k) counts digits after the point instead of significant digits, so cout << fixed << setprecision(4) prints 66.6667, 10.0000, 1234567.0000. The rounding works on the stored value, not on the decimal written in the program. When a problem accepts an error of 10^{-6}, print with fixed << setprecision(9), 3 digits more than it needs.

To check that integer sides a, b, c form a right triangle, compare a * a + b * b with c * c in long long, without square roots or angles.

In C++

The template keeps the tolerance, the comparisons and the printing in one place. Going back from a double to an integer, llround(x) rounds to the nearest integer, and floor(x) and ceil(x) round down and up.

#include <cmath>                          // fabs, llround, floor, ceil, sqrt
#include <cstdio>                         // printf
#include <iomanip>                        // fixed, setprecision
#include <iostream>
using namespace std;

const double EPS = 1e-9;                  // for values up to about 10^4

int main() {
    double a, b;
    cin >> a >> b;
    bool equal = fabs(a - b) < EPS;       // a == b
    bool less = a < b - EPS;              // a < b
    bool lessOrEqual = a < b + EPS;       // a <= b
    long long r = llround(a);             // nearest integer
    cout << fixed << setprecision(4) << a << "\n";   // 4 digits after the point
    printf("%.4f\n", a);                  // the same with printf
    cout << equal << " " << less << " " << lessOrEqual << " " << r << "\n";
}

An average

sum / n with two int variables is integer division even when the result is stored in a double, so convert first: (double)sum / n, or 2.0 * v1 * v2 in a longer formula. Scores 8, 9 and 8 add up to 25, and (double)sum / n is 8.333…, printed with 2 digits as 8.33.

int sum = 0;
for (int i = 0; i < n; i++) {
    int s;
    cin >> s;
    sum += s;
}
cout << fixed << setprecision(2) << (double)sum / n << "\n";

Is a number an integer

A number read as a double is an integer when it is within EPS of the nearest integer. For 7.000 the test is true, for -21.121 it is false.

double x;
cin >> x;
bool whole = fabs(x - llround(x)) < EPS;

A square root of a tiny negative

0.3 - 0.1 * 3 should be 0 but is -5.55 \cdot 10^{-17}, so sqrt of it is nan, "not a number" (GCC may print -nan). Clamp the value to 0 first.

double r = sqrt(max(0.0, v));             // v may be a tiny negative

Points on one line

Three points are given with 2 digits after the point, and the program prints YES if they lie on one line. The input has fractions, so use doubles. The points lie on one line when cr below is 0. For (0, 0), (0.1, 0.3) and (0.3, 0.9) it comes out as 1.05 \cdot 10^{-17}.

double cr = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
if (/* compare */) cout << "YES\n";
else cout << "NO\n";

Common mistakes

• Overflow before the conversion. With int values up to 10^9, 2 * v1 * v2 / (v1 + v2) overflows int before anything becomes a double; 2.0 * v1 * v2 / (v1 + v2) converts first and doesn't.

• Using EPS = 1e-9 for large values. Near 10^9 the gap between neighbouring doubles is 1.19 \cdot 10^{-7}, so (1e9 + 0.1) + 0.2 and 1e9 + 0.3 differ by one gap and fabs(a - b) < 1e-9 is false. Choose EPS between the error and the smallest real difference: with inputs of 3 digits after the point, 1e-5 works.

• Rounding down with (int). (int)(2.3 * 100) is 229, because 2.3 * 100 is 229.99999999999997. Use llround, or add EPS before floor.

• Printing a tiny negative error. A value like 0.3 - 0.1 * 3 prints -0.0000 with 4 fixed digits. Set the value to 0 first when fabs(x) < EPS.

• Using float. float f = 16777217; stores 16777216, and 0.1f is 0.10000000149. With about 7 significant digits, a value near 1000 has only about 3 correct digits after the point, too few for answers printed with 4–6; use double.

Similar techniques

• Integer types: a double reaches 10^{308} but keeps only about 15–16 significant digits, so it is not a fix for overflow: 1e16 + 1 == 1e16 is true.

• Integer division gives a whole quotient or a count rounded up, (n + k - 1) / k, with no rounding errors; ceil of a double can be off by one.

• Binary search on real numbers runs a fixed number of iterations, such as 100, instead of while (r - l > EPS), which may never end when EPS is smaller than the gap between neighbouring doubles.

• Exact fractions keep a numerator and a denominator reduced with the Euclidean algorithm, for answers printed as "p/q".

• Big integers hold integers with more significant digits than a double keeps.

Practice