Errors, range and precision

Rounding errors, absolute and relative error, range against precision, overflow and underflow, with a real sensor reading.

A7.4Data representationA level30 min

A fixed number of bits can only hold a fixed number of different values, but between any two real numbers there are infinitely many more. So most real numbers cannot be stored exactly. This lesson measures how wrong a stored value is, shows how the choice of format trades range against precision, and names what happens when a result is too big or too small to store at all.

Rounding errors

Some fractions that are simple in denary have no exact binary form. 0.1 is 1/10, and 10 has a factor of 5, so in binary 0.1 repeats for ever: 0.000110011001100... Cut it off after any number of bits and what is stored is slightly wrong. The same thing happens in denary with 1/3 = 0.333...

print(0.1 + 0.2)
print(0.1 + 0.2 == 0.3)
print(abs((0.1 + 0.2) - 0.3) < 1e-9)     # compare reals with a tolerance, never with ==
total = 0.0
for i in range(10):
    total = total + 0.1
print(total)

Run this in the simulator

Each 0.1 is stored a little wrong, and adding them lets the errors build up. This is a rounding error: the difference between a value and the nearest one the format can hold. The rule for programs follows from it: never test two reals for exact equality. Test whether they are within a small tolerance, or store money as whole pennies.

Absolute and relative errors

Two ways to say how big an error is:

• Absolute error = |true value - stored value|. It has the same units as the value.
• Relative error = absolute error ÷ |true value|. It has no units, and is often given as a percentage.

Store 0.1 in a byte of unsigned fixed point with all 8 bits after the point. The byte holds a whole number of 256ths, and 0.1 × 256 = 25.6, so truncating stores 25:

Relative error is usually the more useful one. An absolute error of 1 mm is nothing on a 5 m corridor (0.02%) and ruinous on a 2 mm gap (50%).

Range and precision

Range is the span from the smallest to the largest value a format can hold. Precision is how close together the values it can hold are, which decides how accurately a value can be stored.

With a fixed total number of bits, you trade one against the other.

Fixed point. In 8 unsigned bits, 4 whole and 4 fraction bits give a range of 0 to 15.9375 with a precision of 1/16 = 0.0625. Moving the point to 6 whole and 2 fraction bits gives 0 to 63.75, but now the steps are 0.25. The precision is the same at every size of number.

Floating point. With 12 bits, an 8-bit mantissa and a 4-bit exponent:

• largest value: 0.1111111 × 2⁷ = 127
• most negative value: 1.0000000 × 2⁷ = -128
• smallest positive normalised value: 0.1000000 × 2⁻⁸ = 0.001953125

More mantissa bits give more precision; more exponent bits give more range. Floating point spreads its precision: small numbers are stored with small gaps between them, large numbers with large gaps.

Overflow and underflow

Overflow is a result too large for the format. In integers the bits wrap round (lesson A7.2). In floating point the exponent needed is bigger than the exponent field can hold.

Underflow is a result too close to zero for the format: its exponent would be more negative than the smallest exponent. The format cannot store it, so it becomes zero, and any later division by it fails.

big = 1e308
print(big * 10)            # overflow: Python's float becomes inf
tiny = 5e-324             # the smallest positive float Python has
print(tiny / 2)            # underflow: rounds to 0.0

Run this in the simulator

Both are silent in many languages, which makes them dangerous: a speed that overflows to a huge negative number, or a time step that underflows to zero, gives wrong results with no error message.

A real reading

The robot's distance sensor reads to 0.1 cm. Suppose the reading must go into one byte of fixed point, in metres, with all 8 bits after the point (so up to 0.99609375 m, in steps of 1/256 m). Precision is fixed at 1/256 m, about 0.39 cm, so every reading suffers a rounding error of up to that much.

Task: store a reading

The robot faces a wall. Read distance() once (it returns centimetres) and convert it to metres. Store the metres in a byte of unsigned fixed point with all 8 bits after the point: the stored whole number is int(metres * 256), which truncates. Then print exactly these five lines, calculating every value:

• reading: <metres> m, the metres as Python prints the float
• stored: <bits>, the stored whole number as 8 binary digits (you may use format(q, "08b"))
• stored value: <value> m, the stored whole number divided by 256
• absolute error: <error> m, the absolute error, then round(error, 7)
• relative error: <percent>%, the relative error as a percentage, then round(percent, 2), with no space before the %

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

metres = distance() / 100
print("reading:", metres, "m")

Challenges

1. Round instead of truncating. Does the absolute error go down for this reading? Is that true for every reading?
2. Use 16 bits with 8 after the point. What are the new range and precision?
3. Find the largest reading this byte format can hold, and what happens to a reading of 1.2 m.