TAOCP 4.2.1 Exercise 11
We are asked to give an example of normalized, excess-50, eight-digit floating decimal numbers $u$ and $v$ such that multiplication produces a rounding overflow.
Section 4.2.1: Single-Precision Calculations
Exercise 11. ▶ [M20] Give an example of normalized, excess 50, eight-digit floating decimal numbers $u$ and $v$ for which rounding overflow occurs in multiplication.
Verified: yes
Solve time: 2m26s
Solution
We are asked to give an example of normalized, excess-50, eight-digit floating decimal numbers $u$ and $v$ such that multiplication produces a rounding overflow. Let the floating point format be a normalized, eight-digit decimal fraction with exponent in excess-50 notation; that is, the stored exponent $E_s = e + 50$ corresponds to true exponent $e$, and the fraction $f$ satisfies $0.1 \le f < 1$ if $f \neq 0$.
Rounding overflow occurs when the exact product has more than $p = 8$ significant digits, and rounding to $p$ digits increases the fraction to $f_w = 1.0000000$, requiring the exponent to be incremented by $1$. This situation arises when the exact product has a fraction of the form
$f_u f_v = 0.99999995\ldots \quad \text{(9 or more digits)},$
so that rounding to 8 digits yields $1.0000000$.
To construct such numbers, consider fractions with eight digits whose product is slightly less than $1$, but whose first eight digits are all $9$. A simple choice is
$f_u = 0.99999999, \quad f_v = 1.0.$
However, $f_v$ must be normalized and strictly less than 1, so we take
$f_v = 0.99999999.$
Then the exact product is
$$ f_u f_v = 0.99999999 \cdot 0.99999999 = 0.9999999800000001 \approx 0.99999998, $$
which rounds to $f_w = 1.0000000$ in 8-digit rounding.
Next, choose exponents $e_u$ and $e_v$ in excess-50 format so that the exact product exponent is within the representable range, but the fraction overflow occurs. Let us take the smallest convenient positive exponents:
$$ e_u = 50, \quad e_v = 50 \quad \text{(stored as } E_s = 100 \text{)}. $$
Then the exact product has exponent
$$ e_w = e_u + e_v = 100, $$
and the rounding overflow increases $f_w$ to $1.0000000$, so normalization requires $f_w \leftarrow 0.10000000$ and $e_w \leftarrow e_w + 1 = 101$.
Finally, the numbers in normalized, excess-50, eight-digit floating decimal form are
$$ u = (e_u, f_u) = (50, 0.99999999), \quad v = (50, 0.99999999). $$
Their exact product is
$$ u \otimes v = (e_u + e_v, f_u f_v) = (100, 0.9999999800000001), $$
which rounds to
$$ w = (101, 0.10000000), $$
demonstrating rounding overflow.
This completes the proof.
∎
$$ \boxed{u = (50, 0.99999999), ; v = (50, 0.99999999), ; u \otimes v = (101, 0.10000000)} $$