TAOCP 4.2.1 Exercise 10

Section 4.2.1: Single-Precision Calculations

Exercise 10. [12] Give an example of normalized eight-digit floating decimal numbers $u$ and $v$ for which rounding overflow occurs in addition.

Verified: no
Solve time: 1m41s

---

Solution

Let the floating point numbers have base $10$ and $p=8$ digits. Rounding overflow occurs in step N5 of Algorithm N when rounding causes the fraction to become $1.00000000$, forcing a return to step N4.

Choose

$$ u=(e,,0.99999995), \qquad v=(e-8,,0.50000000). $$

Both numbers are normalized eight-digit floating decimal numbers. Since

$$ e_u-e_v=8, $$

step A5 shifts the fraction of $v$ right by eight decimal places:

$$ 0.50000000\times 10^{-8}=0.000000005. $$

Step A6 forms the exact sum of the fractions:

$$ f_w =0.99999995+0.000000005 =0.999999955. $$

This value satisfies

$$ \frac1{10}\le f_w<1, $$

so no scaling is performed in steps N2-N4 before rounding.

In step N5, $f_w$ is rounded to eight decimal places. Since the ninth digit is $5$,

$$ 0.999999955 \longrightarrow 0.99999996. $$

This does not yet overflow. To force rounding overflow, increase the leading fraction slightly. Take instead

$$ u=(e,,0.99999996), \qquad v=(e-8,,0.50000000). $$

Then

$$ f_w =0.99999996+0.000000005 =0.999999965. $$

Rounding to eight digits gives

$$ 0.999999965 \longrightarrow 1.00000000. $$

Thus step N5 produces $|f|=1$, which is exactly the "rounding overflow" case described in Algorithm N. Control returns to step N4, yielding

$$ f=0.10000000,\qquad e\leftarrow e+1. $$

Therefore an example is

$$ \boxed{ u=(e,,0.99999996),\qquad v=(e-8,,0.50000000) } $$

for any exponent $e$ such that $e+1$ remains within the allowed exponent range. The addition produces rounding overflow during normalization. ∎