จำนวนทศนิยม (Floating-point numbers)

A missile that missed by 600 metres

• On 25 February 1991 a Patriot battery at Dhahran failed to intercept an incoming missile. Twenty-eight soldiers died.
• The system counted time in tenths of a second, and 0.1 has no exact binary representation: it is a repeating fraction, truncated to the register's width. Each tick lost a fraction of a microsecond.
• After a hundred hours running, the accumulated error was a third of a second, and in a third of a second the target moved 600 metres. The arithmetic was correct at every single step.
• This lesson is the floating-point 浮点 format, normalisation 规格化, and the approximation errors that make cases like this possible.

The format

• To store real numbers of very different sizes, a computer uses a binary form of scientific notation with two fields: a mantissa 尾数, the significant digits, and an exponent 指数, the power of 2 to multiply by. Both are stored as two's complement.

• Read the mantissa as a binary fraction: the first bit after the point is worth $\tfrac12$, the next $\tfrac14$, then $\tfrac18$. So 0.1010000 is $\tfrac12 + \tfrac18 = 0.625$.
• With exponent 00000010, that is $+2$, the value is $0.625 \times 2^2 = 2.5$.

A fraction and a power of two

Worked example: binary to denary

Worked example: denary to binary

Normalisation

• A number is normalised when the first significant bit sits immediately after the binary point, so there are no wasted leading zeros. For a positive number the mantissa starts 0.1; for a negative one, 1.0.
• Why: it maximises precision 精度, because every mantissa bit then carries information rather than a leading zero.
• To normalise, shift the mantissa left and decrease the exponent by the same number of places, or shift right and increase it. The value is unchanged; only its representation is.

Shift the bits, adjust the exponent, keep the value

Trading mantissa bits against exponent bits

• The total number of bits is fixed, so the two fields compete.
• More mantissa bits means greater precision: each value is stored more exactly, with a smaller rounding error.
• More exponent bits means greater range: much larger and much smaller magnitudes can be represented, but each one less precisely.
• A question asking for the effect of moving a bit from one field to the other wants exactly this trade: range against precision.

Approximation and its consequences

• Many denary reals cannot be stored exactly in binary. $0.1$ is the repeating fraction $0.000110011\ldots$, so it must be truncated: the stored value is close to $0.1$ but never equal to it.
• Rounding errors 舍入误差 accumulate over many operations, which is why 0.1 + 0.2 is not exactly 0.3 and why the Patriot's clock drifted.
• So never test two reals for equality: write ABS(x - 0.3) < 1e-9 instead of x = 0.3. And beware subtracting two nearly equal values, which throws away most of the significant digits.
• For values that must be exact, currency above all, use fixed-point 定点 or BCD instead.

Overflow and underflow

• Overflow 溢出 happens when a result is too large for the exponent's range, so it cannot be represented at all.
• Underflow 下溢 happens when a result is too small, so close to zero that the exponent cannot go low enough, and it rounds to zero.
• Both are properties of the exponent field's size, which is the other half of the trade-off above.

Marks that slip away

You've got it