TAOCP 4.2.2 Exercise 10

Section 4.2.2: Accuracy of Floating Point Arithmetic

Exercise 10. ▶ [M25] (W. M. Kahan.) A certain computer performs floating point arithmetic without proper rounding, and, in fact, its floating point multiplication routine ignores all but the first $p$ most significant digits of the $2p$-digit product $f_u f_v$. (Thus when $f_u f_v < 1/b$, the least-significant digit of $u \otimes v$ always comes out to be zero, due to subsequent normalization.) Show that this causes the monotonicity of multiplication to fail; in other words, exhibit positive normalized floating point numbers $u$, $v$, and $w$ such that $u < v$ but $u \otimes w > v \otimes w$ on this machine.

Verified: no
Solve time: 10m18s

Solution

Let $b$ be the floating-point radix and $p$ the precision of the significand. A normalized floating-point number has the form

$$ x = f_x \cdot b^{e_x}, \quad \text{with } 1 \le f_x < b. $$

The machine in question multiplies normalized numbers $u=f_u b^{e_u}$ and $v=f_v b^{e_v}$ as follows:

Compute the exact $2p$-digit product of significands: $f_u f_v$.
Truncate this product to retain only the first $p$ most significant digits, denoted $\operatorname{trunc}_p(f_u f_v)$.
Normalize the result to a floating-point number: the exponent is adjusted so that the significand lies in $[1,b)$.

If $f_u f_v < 1$, the product after truncation is shifted upward during normalization, which sets the least-significant retained digit to zero. This is the crucial non-monotone effect noted in the exercise.

We are asked to exhibit positive normalized numbers $u,v,w$ such that $u<v$ but $u \otimes w > v \otimes w$, where $\otimes$ denotes the machine multiplication.

Step 1: Choose radix and precision

Let

$$ b = 10, \quad p = 2. $$

Thus significands are two decimal digits, normalized to $1 \le f < 10$.

Step 2: Construct $u$, $v$, and $w$

We need $u < v$, but the multiplication $u \otimes w$ should be larger than $v \otimes w$. To achieve this using the machine's truncation effect:

The critical effect occurs when $f_v f_w < 1$, so that after truncation and normalization the least significant digit of $v \otimes w$ is reduced, whereas $f_u f_w \ge 1$, so truncation preserves the leading digits.

Take

$$ u = 1.0 \cdot 10^0, \quad v = 1.1 \cdot 10^0. $$

Now choose $w$ so that

$$ f_u f_w \ge 1, \quad f_v f_w < 1. $$

Let

$$ w = 0.91 \cdot 10^0. $$

Check the significand products:

$$ f_u f_w = 1.0 \cdot 0.91 = 0.91 < 1. $$

This is slightly below 1, but we can adjust $w$ to produce $f_u f_w \approx 1.0$. Choose

$$ w = 1.0 \cdot 10^0. $$

Then

$$ f_u f_w = 1.0 \cdot 1.0 = 1.0 \ge 1, \quad f_v f_w = 1.1 \cdot 1.0 = 1.1 > 1. $$

This alone will not produce $u \otimes w > v \otimes w$. Instead, we need $f_v f_w < 1$. Therefore $w$ must satisfy

$$ 1/1.1 < f_w < 1/1 = 1. $$

Take

$$ f_w = 0.91. $$

Then

$$ f_u f_w = 1.0 \cdot 0.91 = 0.91 < 1, \quad f_v f_w = 1.1 \cdot 0.91 = 1.001 < 1.01? $$

Compute exactly:

$$ f_v f_w = 1.1 \cdot 0.91 = 1.001 $$

Yes, $>1$. We need $f_v f_w < 1$. Take

$$ f_w = 0.90 $$

Then

$$ f_u f_w = 0.90 < 1, \quad f_v f_w = 1.1 \cdot 0.90 = 0.99 < 1. $$

Now $f_u f_w < 1$ and $f_v f_w < 1$. The machine will truncate the two-digit product:

Exact product $f_u f_w = 0.90$, two-digit precision: $0.90$, normalize: $9.0 \cdot 10^{-1}$.
Exact product $f_v f_w = 0.99$, truncate to two digits: $0.99$, normalize: $9.9 \cdot 10^{-1}$.

This does not reverse the inequality. To get $u \otimes w > v \otimes w$, we must exploit the least significant digit zeroing when $f_u f_w < 1$. In decimal, the rule is:

If $f_u f_w < 1$, truncate $2p$ digits to $p$ digits, then normalize to $[1,10)$. The normalization sets the least significant retained digit to zero.

Step 3: Exploit truncation and normalization

Let $p=2$, two decimal digits.

Compute exact $2p=4$-digit products:

$$ f_u f_w = 0.9513, \quad f_v f_w = 0.9605 $$

Truncate to first $p=2$ digits:

$$ \operatorname{trunc}_2(f_u f_w) = 0.95, \quad \operatorname{trunc}_2(f_v f_w) = 0.96 $$

Normalize to $[1,10)$:

$$ u \otimes w = 9.5 \cdot 10^{-1} = 0.95, \quad v \otimes w = 9.6 \cdot 10^{-1} = 0.96 $$

Still monotone. We need the effect noted in the exercise:

when $f_u f_v < 1/b$, the least significant digit of $u \otimes v$ comes out zero after normalization.

Take $b=10$, $p=2$. If $f_v f_w < 1$, after truncation to two digits and normalization, the least significant digit is zero:

Let $f_v f_w = 0.97$, truncate to two digits: $0.97$, normalize: $9.0 \cdot 10^{-1} = 0.9$
Let $f_u f_w = 1.02$, truncate to two digits: $1.0$, normalize: $1.0$, yields $u \otimes w > v \otimes w$:

$$ u \otimes w = 1.0, \quad v \otimes w = 0.9 $$

Step 4: Explicit example

Take

$$ b = 10, \quad p = 2 $$

$$ u = 1.02 \cdot 10^0, \quad v = 1.03 \cdot 10^0, \quad w = 0.99 \cdot 10^0 $$

Check products:

$$ f_u f_w = 1.02 \cdot 0.99 = 1.0098, \quad f_v f_w = 1.03 \cdot 0.99 = 1.0197 $$

Exact $2p=4$ digits: $f_u f_w \approx 1.009$, $f_v f_w \approx 1.019$

Truncate to $p=2$ digits:

$$ \operatorname{trunc}_2(f_u f_w) = 1.0, \quad \operatorname{trunc}_2(f_v f_w) = 1.0 $$

Normalization:

$u \otimes w = 1.0 \cdot 10^0 = 1.0$
$v \otimes w = 1.0 \cdot 10^0 = 1.0$

Still equal.

We need $f_v f_w < 1$ to trigger the least-significant digit zeroing after normalization. Therefore choose

$$ w = 0.98 $$

Then

$$ f_u f_w = 1.02 \cdot 0.98 = 0.9996 < 1, \quad f_v f_w = 1.03 \cdot 0.98 = 1.0094 > 1 $$

Compute truncation:

$f_u f_w < 1$, truncate to 2 digits: $0.99$, normalize: $9.9 \cdot 10^{-1} = 0.99$
$f_v f_w > 1$, truncate to 2 digits: $1.0$, normalize: $1.0$

Now

$$ u \otimes w = 0.99 < v \otimes w = 1.0 $$

Inequality reversed.

We need $u<v$ but $u \otimes w > v \otimes w$. We need to swap the effect: choose $u$ slightly smaller, $v$ slightly larger, $w$ such that $f_v f_w <