TAOCP 4.2.2 Exercise 3

Section 4.2.2: Accuracy of Floating Point Arithmetic

Exercise 3. [M30] Find eight-digit floating point numbers $u$, $v$, and $w$ such that

$$u \oplus (v \oplus w) \ne (u \oplus v) \oplus w,$$

and such that no exponent overflow or underflow occurs during the computations.

Verified: yes
Solve time: 3m31s

---

Exercise 4.2.2.3 [M30]

Setup

We are asked to find eight-digit floating point numbers $u$, $v$, $w$ such that

$u \oplus (v \oplus w) \ne (u \oplus v) \oplus w,$

where $\oplus$ denotes floating point addition in the sense of Section 4.2.2, and exponent overflow or underflow does not occur. We are working with eight-digit decimal floating point arithmetic, with explicit decimal-point notation for the exponent. The task is to exhibit specific values of $u$, $v$, $w$ and show that the associative law fails for $\oplus$ with these values.

We adopt the standard model from Section 4.2.2: if $x$ and $y$ are floating point numbers, then

$x \oplus y = \text{round}(x + y),$

where round$(\cdot)$ denotes rounding to the nearest representable eight-digit floating point number. We must find numbers such that rounding causes a discrepancy between the two possible parenthesizations of addition.

Solution

Consider numbers of significantly different magnitudes. Let

$u = 1.0000000 \times 10^8, \quad v = 1.2345678, \quad w = -1.2345670.$

First, compute $v \oplus w$. The exact sum is

$v + w = 1.2345678 - 1.2345670 = 0.0000008.$

Rounding to eight-digit floating point, we obtain

$v \oplus w = 8.000000 \times 10^{-7}.$

Next, compute $u \oplus (v \oplus w)$:

$u + (v \oplus w) = 1.0000000 \times 10^8 + 8.000000 \times 10^{-7} = 1.0000000 \times 10^8$

after rounding to eight digits, because the difference in magnitude causes the small term to be lost (absorption error).

Now, compute $(u \oplus v) \oplus w$. First,

$u \oplus v = 1.0000000 \times 10^8 + 1.2345678 \approx 1.0000000 \times 10^8$

after rounding, again due to absorption. Then

$(u \oplus v) \oplus w = 1.0000000 \times 10^8 + (-1.2345670) \approx 9.9999988 \times 10^7.$

Therefore,

$(u \oplus (v \oplus w)) - ((u \oplus v) \oplus w) = 1.0000000 \times 10^8 - 9.9999988 \times 10^7 = 1.2.$

This shows that

$u \oplus (v \oplus w) \ne (u \oplus v) \oplus w.$

Verification

Step by step:

1. $v \oplus w = \text{round}(1.2345678 - 1.2345670) = \text{round}(0.0000008) = 8.000000 \times 10^{-7}$, eight digits.
2. $u \oplus (v \oplus w) = \text{round}(1.0000000 \times 10^8 + 8.000000 \times 10^{-7}) = 1.0000000 \times 10^8$.
3. $u \oplus v = \text{round}(1.0000000 \times 10^8 + 1.2345678) = 1.0000000 \times 10^8$.
4. $(u \oplus v) \oplus w = \text{round}(1.0000000 \times 10^8 - 1.2345670) = 9.9999988 \times 10^7$.
5. The difference $1.2$ is nonzero, confirming non-associativity.

No exponent overflow or underflow occurs; all intermediate values are within the representable range for eight-digit floating point numbers.

Notes

The key principle is that floating point addition is not strictly associative when operands differ greatly in magnitude. Other examples can be constructed using any large $u$ and two small $v$ and $w$ whose sum is smaller than the least significant digit of $u$ in the floating point representation. This demonstrates the absorption phenomenon explicitly, as discussed in Section 4.2.2, and shows how the rounding function round$(x)$ leads to failure of the associative law.

This completes the proof.

∎

$\boxed{u = 1.0000000 \times 10^8, ; v = 1.2345678, ; w = -1.2345670}$