TAOCP 4.2.2 Exercise 8

Section 4.2.2: Accuracy of Floating Point Arithmetic

Exercise 8. ▶ [20] Let $\epsilon = 0.0001$; which of the relations

$$u < v \quad \text{(c)}, \qquad u \sim v \quad \text{(c)}, \qquad u > v \quad \text{(c)}, \qquad u \approx v \quad \text{(c)}$$

hold for the following pairs of one's complement, eight-digit floating point numbers?

a) $u = (1, +.34415927)$, $v = (1, +.31416000)$;

b) $u = (0, +.99997000)$, $v = (1, +.10000039)$;

c) $u = (24, +.60221400)$, $v = (27, +.00006022)$;

d) $u = (24, +.60221400)$, $v = (31, +.10000000)$;

e) $u = (24, +.60221400)$, $v = (28, +.10000000)$.

Verified: yes
Solve time: 3m52s

Solution

We are asked to determine which of the relations

$u < v, \qquad u \sim v, \qquad u > v, \qquad u \approx v$

hold for the given pairs of eight-digit, one's-complement floating point numbers, assuming $\epsilon = 0.0001$. Recall that in one's-complement representation, the sign is indicated separately and the value of a number $(s, m)$ is

$(-1)^s \times m,$

where $m$ is the fractional part and $0 \le m < 1$ for normalized numbers. Relations $u \sim v$ and $u \approx v$ are defined by Section 4.2.2 as follows:

$u \sim v$ means that $u$ and $v$ are nearly equal in the sense that their difference is negligible relative to $\epsilon$, i.e., $|u - v| < \epsilon$.
$u \approx v$ means that $u$ and $v$ are approximately equal, typically within the rounding tolerance of the floating point system. For eight-digit normalized floating point numbers, $u \approx v$ if their difference is smaller than the ulp for the smaller exponent.

We now consider each pair separately.

a) $u = (1, +.34415927)$, $v = (1, +.31416000)$.

Both numbers have sign $1$, so they are negative. Their magnitudes are

$|u| = 0.34415927, \qquad |v| = 0.31416000.$

Since $|u| > |v|$ and both are negative, we have

$u = -0.34415927 < -0.31416000 = v.$

Hence the relations satisfied are

$u < v.$

The difference $|u - v| = 0.02999927 \gg \epsilon$, so $u \sim v$ and $u \approx v$ do not hold. Also, $u > v$ is false.

b) $u = (0, +.99997000)$, $v = (1, +.10000039)$.

Here $u$ is positive, $v$ is negative:

$u = +0.99997000, \qquad v = -0.10000039.$

Clearly $u > v$, and $|u - v| = 1.09997039 \gg \epsilon$, so neither $u \sim v$ nor $u \approx v$ hold. $u < v$ is false.

c) $u = (24, +.60221400)$, $v = (27, +.00006022)$.

The exponents differ: $u$ has exponent $24$, $v$ has exponent $27$. Converting to magnitude:

$|u| = 0.602214 \times b^{24}, \qquad |v| = 0.00006022 \times b^{27}.$

Assuming $b = 10$, we compute

$|u| = 0.602214 \cdot 10^{24} = 6.02214 \cdot 10^{23},$

$|v| = 0.00006022 \cdot 10^{27} = 6.022 \cdot 10^{22}.$

Both numbers are positive, so $u > v$. The relative difference is

$\frac{|u - v|}{u} = \frac{6.02214 \cdot 10^{23} - 6.022 \cdot 10^{22}}{6.02214 \cdot 10^{23}} \approx 0.90 \gg \epsilon.$

Hence neither $u \sim v$ nor $u \approx v$ hold.

d) $u = (24, +.60221400)$, $v = (31, +.10000000)$.

Both numbers are positive. Magnitudes:

$|u| = 6.02214 \cdot 10^{23}, \qquad |v| = 1.0 \cdot 10^{31}.$

Clearly $u < v$, and the relative difference is enormous compared to $\epsilon$, so $u \sim v$ and $u \approx v$ do not hold. $u > v$ is false.

e) $u = (24, +.60221400)$, $v = (28, +.10000000)$.

Both positive, compute magnitudes:

$|u| = 6.02214 \cdot 10^{23}, \qquad |v| = 1.0 \cdot 10^{28}.$

Thus $u < v$, and the difference is far larger than $\epsilon$, so $u \sim v$ and $u \approx v$ are false. $u > v$ is false.

We summarize the results:

Pair	$u < v$	$u > v$
a	✓
b		✓
c		✓
d	✓
e	✓

This completes the solution.

∎