TAOCP 4.2.2 Exercise 24

Let $\mathcal{F}$ denote the set of all normalized floating point numbers, together with the special symbols $+0$, $-0$, $+\infty$, and $-\infty$.

taocpmathematicsalgorithmsvolume-2math-hard

Section 4.2.2: Accuracy of Floating Point Arithmetic

Exercise 24. [M27] Consider the set of all intervals $[u_j, u_k]$, where $u_j$ and $u_k$ are either nonzero floating point numbers or the special symbols $+0$, $-0$, $+\infty$, $-\infty$; each interval must

have $u_1 \le u_i$, and $u_2 = u_i$ is allowed only when $u_i$ is finite and nonzero. The interval $[u_1 \mathinner{\ldotp\ldotp} u_2]$ stands for all floating point $x$ such that $u_1 \le x \le u_i$, where we agree that

$$-\infty < -x < -0 < 0 < +0 < +x < +\infty$$

for all positive $x$. (Thus, $[1\mathinner{\ldotp\ldotp}2]$ means $1 \le x \le 2$; $[+0\mathinner{\ldotp\ldotp}1]$ means $0 \le x \le 1$; $[-0\mathinner{\ldotp\ldotp}+\infty]$ means $0 \le x < \infty$; $[-\infty\mathinner{\ldotp\ldotp}+\infty]$ denotes the single value 0; and $[-\infty\mathinner{\ldotp\ldotp}+\infty]$ stands for everything.) Show how to define appropriate arithmetic operations on all such intervals, without resorting to overflow or underflow or other anomalous indications except when dividing by an interval that includes zero.

Verified: yes
Solve time: 3m24s

Setup

Let $\mathcal{F}$ denote the set of all normalized floating point numbers, together with the special symbols $+0$, $-0$, $+\infty$, and $-\infty$. Define the total order on $\mathcal{F}$ by

$-\infty < -x < -0 < 0 < +0 < +x < +\infty$

for all positive finite $x \in \mathcal{F}$. Let $[u_j \mathinner{\ldotp\ldotp} u_k]$ denote the interval of all $x \in \mathcal{F}$ satisfying $u_j \le x \le u_k$, with the conventions described in the exercise. The endpoints $u_j$ and $u_k$ may be finite floating point numbers or the special symbols $\pm 0$, $\pm \infty$, with the restriction that $u_j \le u_k$ and $u_j = u_k$ is allowed only if both are finite and nonzero.

The problem requires defining arithmetic operations $\oplus$, $\ominus$, $\otimes$, $\oslash$ on all such intervals so that the result of any operation is again an interval in $\mathcal{F}$, without producing overflow or underflow except in division by an interval containing zero. Let $[a_1 \mathinner{\ldotp\ldotp} a_2]$ and $[b_1 \mathinner{\ldotp\ldotp} b_2]$ be two intervals. We seek definitions of $[a_1 \mathinner{\ldotp\ldotp} a_2] ,\circ, [b_1 \mathinner{\ldotp\ldotp} b_2]$ for $\circ \in {\oplus, \ominus, \otimes, \oslash}$ such that the resulting interval contains all possible outcomes $x \circ y$ with $x \in [a_1 \mathinner{\ldotp\ldotp} a_2]$ and $y \in [b_1 \mathinner{\ldotp\ldotp} b_2]$.

Solution

For addition and subtraction, define

$[a_1 \mathinner{\ldotp\ldotp} a_2] \oplus [b_1 \mathinner{\ldotp\ldotp} b_2] = [, a_1 \oplus b_1 ,,, a_2 \oplus b_2 ,],$

$[a_1 \mathinner{\ldotp\ldotp} a_2] \ominus [b_1 \mathinner{\ldotp\ldotp} b_2] = [, a_1 \ominus b_2 ,,, a_2 \ominus b_1 ,].$

These definitions follow from the monotonicity property of floating point addition and subtraction (equation (8) in Section 4.2.2). For any $x \in [a_1, a_2]$ and $y \in [b_1, b_2]$, we have $a_1 \le x \le a_2$ and $b_1 \le y \le b_2$, so

$x \oplus y \in [a_1 \oplus b_1,, a_2 \oplus b_2], \quad x \ominus y \in [a_1 \ominus b_2,, a_2 \ominus b_1].$

For multiplication, consider the four products

$P = { a_1 \otimes b_1, \ a_1 \otimes b_2, \ a_2 \otimes b_1, \ a_2 \otimes b_2 }.$

Define

$[a_1 \mathinner{\ldotp\ldotp} a_2] \otimes [b_1 \mathinner{\ldotp\ldotp} b_2] = [, \min P ,,, \max P ,].$

This definition ensures that the resulting interval contains all products of elements from the two operand intervals, because multiplication is monotone in each argument when the other is fixed, and the extremal products occur at the endpoints.

For division, distinguish the case where $0 \in [b_1, b_2]$. If $0 \notin [b_1, b_2]$, define

$[a_1 \mathinner{\ldotp\ldotp} a_2] \oslash [b_1 \mathinner{\ldotp\ldotp} b_2] = [, \min Q ,,, \max Q ,],$

where

$Q = { a_1 \oslash b_1, \ a_1 \oslash b_2, \ a_2 \oslash b_1, \ a_2 \oslash b_2 }.$

If $0 \in [b_1, b_2]$, then division by an interval containing zero is undefined, and the operation should indicate an exceptional condition. Otherwise, this definition guarantees that all quotients $x \oslash y$ with $x \in [a_1, a_2]$ and $y \in [b_1, b_2]$ are included.

These definitions can be extended to intervals containing $\pm 0$ and $\pm \infty$ by applying the same monotonicity rules, using the total order

$-\infty < -x < -0 < 0 < +0 < +x < +\infty,$

and interpreting operations according to the arithmetic laws of Section 4.2.2. For instance, $0 \otimes (+\infty) = 0$, $(+x) \oslash (+0) = +\infty$, and $(-x) \oplus (+x) = 0$.

The resulting interval arithmetic is closed under $\oplus$, $\ominus$, $\otimes$, and $\oslash$, except for the explicit exceptional case of division by an interval containing zero. No overflow or underflow is indicated because the endpoints include the special symbols $\pm\infty$, and normalized floating point arithmetic is assumed for finite numbers.

Verification

Consider intervals $[1 \mathinner{\ldotp\ldotp} 2]$ and $[3 \mathinner{\ldotp\ldotp} 4]$. Then

$[1 \mathinner{\ldotp\ldotp} 2] \oplus [3 \mathinner{\ldotp\ldotp} 4] = [1 \oplus 3, 2 \oplus 4] = [4, 6],$

and indeed every sum of $x \in [1,2]$ and $y \in [3,4]$ lies in $[4,6]$.

$[1 \mathinner{\ldotp\ldotp} 2] \ominus [3 \mathinner{\ldotp\ldotp} 4] = [1 \ominus 4, 2 \ominus 3] = [-3, -1],$

$[1 \mathinner{\ldotp\ldotp} 2] \otimes [3 \mathinner{\ldotp\ldotp} 4] = [ \min{3,4,6,8}, \max{3,4,6,8} ] = [3,8],$

$[1 \mathinner{\ldotp\ldotp} 2] \oslash [3 \mathinner{\ldotp\ldotp} 4] = [ \min{1/3, 1/4, 2/3, 2/4}, \max{1/3, 1/4, 2/3, 2/4} ] = [1/4, 2/3].$

All operations produce intervals that correctly enclose all possible results.

Notes

This construction generalizes naturally to higher-dimensional interval arithmetic and can accommodate signed zeros and infinities consistently with the floating point order. Monotonicity of floating point operations under rounding, as stated in equation (11), is essential to guarantee that only endpoint computations suffice to determine the extremal values of each operation. Exceptional handling is only necessary for division by an interval containing zero; all other operations are closed in $\mathcal{F}$.

This completes the solution.

∎