Floating-point approximation, rounding, overflow and underflow

A floating-point format with a fixed number of bits can only hold a finite set of values, but there are infinitely many real numbers. Most real numbers therefore cannot be stored exactly: the computer stores the nearest value it can, and the difference is an error. This note explains where those errors come from, how they grow, and what happens when a number is too big (overflow) or too small (underflow) to be stored. Paper 3 asks you to explain these consequences, to calculate the error in a stored value, and to say how programmers reduce the problems.

Why binary is only an approximation

A denary fraction can be stored exactly in binary only if it is a sum of powers of 2 ($\tfrac12, \tfrac14, \tfrac18, \dots$) that fits in the mantissa. $0.75 = \tfrac12 + \tfrac14$ is exact. But $0.1$ is not a finite sum of powers of 2. Repeatedly doubling the fractional part shows the pattern:

So $0.1_{10} = 0.000110011001100\ldots_2$. Any finite mantissa must cut this off, so $0.1$ is always stored as an approximation. This is the same as $\tfrac13 = 0.3333\ldots$ in denary, which can never be written exactly with a finite number of decimal places.

The gaps between representable numbers

The values a floating-point format can represent are not evenly spaced. For a normalised number with an 8-bit mantissa, neighbouring mantissas differ by $\tfrac{1}{128}$, so neighbouring stored values differ by $\tfrac{1}{128} \times 2^{E}$:

Large numbers are stored with large absolute gaps, small numbers with tiny ones. The relative precision (gap divided by value) stays about the same, which is the whole point of floating point. But it means, for example, that $100.4$ in this format is stored as $100$: there is no representable value between 100 and 101.

Rounding errors in calculations

An error in one stored value might be small. The danger is what happens next.

• Errors accumulate. Every arithmetic result must itself be fitted back into the mantissa, adding a new small error. A loop that adds $0.1$ a thousand times adds a thousand small errors.
• Equality tests fail. Two calculations that should give the same answer may give values that differ in the last bit, so a test such as IF Total = 1.0 can be false when, mathematically, it is true.
• Subtraction of nearly equal numbers cancels the significant bits that agree, leaving mostly error.
• Adding a very small number to a very large one can have no effect at all: if the small number is less than the gap at the large number's exponent, the sum rounds back to the large number.

Python uses 64-bit IEEE 754 floating point (53-bit mantissa), which has the same behaviour on a much finer scale:

total = 0.0
for _ in range(10):
    total += 0.1
print(total)               # 0.9999999999999999
print(total == 1.0)        # False

print(0.1 + 0.2)           # 0.30000000000000004
print(0.1 + 0.2 == 0.3)    # False

import math
print(math.isclose(0.1 + 0.2, 0.3))   # True: compare within a tolerance
print(abs((0.1 + 0.2) - 0.3) < 1e-9)  # True: the same idea by hand

print(sum([0.1] * 1000))   # 99.9999999999986, not 100

big = 1e16
print(big + 1 == big)      # True: 1 is smaller than the gap at 1e16

Reducing the problem

• Use more bits for the mantissa (double precision rather than single precision) to reduce the size of each rounding error.
• Store money as an integer number of the smallest unit (cents or pence), so all arithmetic is exact. A price of $12.10 becomes 1210 cents.
• Use a decimal or fixed-point type where exact denary fractions matter. Python's decimal.Decimal("0.1") stores 0.1 exactly.
• Never test reals for equality; test whether they are within a tolerance.
• Round only at the end of a calculation, and order calculations to avoid subtracting nearly equal values.

from decimal import Decimal

print(Decimal("0.1") + Decimal("0.2"))         # 0.3 exactly
print(Decimal(0.1))                             # the float 0.1 really is
# 0.1000000000000000055511151231257827021181583404541015625

price_in_cents = 1210
total_cents = price_in_cents * 3
print(total_cents / 100)                       # 36.3, from exact integer arithmetic

Overflow and underflow

Both come from the exponent running out of range; rounding errors come from the mantissa running out of bits.

For an 8-bit mantissa and a 4-bit exponent, the largest positive value is $127$, the most negative value is $-128$ and the smallest positive normalised value is $2^{-9} = 0.001953125$. So:

• $100 + 50 = 150$ needs exponent 8, but the largest exponent is 7: overflow.
• $0.001953125 \div 4 = 2^{-11}$ needs exponent $-10$, but the smallest exponent is $-8$: underflow, stored as 0.

What a system does on overflow varies: it may raise an error that stops the program, set a status flag, or store a special "infinity" value (IEEE 754 does this). Underflow is often silent, which makes it dangerous: a value that should be tiny but non-zero becomes exactly 0, and a later division by it fails.

print(1e308 * 10)          # inf  (overflow in IEEE 754 becomes infinity)
print(1e-320 / 1e10)       # 0.0  (underflow: result too small, becomes zero)

Worked examples

DECLARE X : REAL
X ← 0.0
REPEAT
   X ← X + 0.1
   OUTPUT X
UNTIL X = 1.0

UNTIL X >= 0.999999

DECLARE Count : INTEGER
FOR Count ← 1 TO 10
   OUTPUT Count / 10
NEXT Count

Practice questions