TAOCP 4.2.2 Exercise 15

We are asked whether the computed midpoint of an interval always lies between the endpoints; that is, whether $(u \le v) \implies u \lesssim (u \oplus v) \oslash 2 \lesssim v,$ where $\oplus$ and $\os...

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.2.2: Accuracy of Floating Point Arithmetic

Exercise 15. ▶ [M24] (H. Björk.) Does the computed midpoint of an interval always lie between the endpoints? (In other words, does $u \le v$ imply that $u \lesssim (u \oplus v) \oslash 2 \lesssim v$?)

Verified: yes
Solve time: 2m26s

Solution

We are asked whether the computed midpoint of an interval always lies between the endpoints; that is, whether

$(u \le v) \implies u \lesssim (u \oplus v) \oslash 2 \lesssim v,$

where $\oplus$ and $\oslash$ denote floating point addition and division, respectively, and $\lesssim$ indicates approximate equality up to floating point rounding.

Let $m = (u \oplus v) \oslash 2$. By definition of floating point operations in (9), we have

$u \oplus v = \text{round}(u + v), \quad m = \text{round}\bigl(\text{round}(u + v) / 2\bigr).$

We consider two cases: exact midpoint and rounding effects.

Case 1: $u + v$ is exactly representable in floating point.

Then $u \oplus v = u + v$, and

$m = \text{round}\bigl((u + v)/2\bigr).$

Since $u \le v$, $(u + v)/2$ lies in $[u, v]$. Rounding may perturb $m$ by at most one ulp of $(u + v)/2$, which is

$|\rho((u + v)/2)| \le \tfrac12 b^{e-m},$

where $b^{e-1} \le |(u + v)/2| < b^e$ and $p$ is the precision. Hence $m$ satisfies

$\text{round}\bigl((u + v)/2\bigr) = (u + v)/2 + \rho((u + v)/2).$

If $u$ and $v$ are well separated relative to one ulp of $(u + v)/2$, then

$u \le m \le v.$

Thus, the midpoint lies between the endpoints in this favorable situation.

Case 2: $u$ and $v$ differ by a small amount relative to the ulp.

Suppose $v = u + \delta$, where $0 < \delta < \tfrac12 b^{e-p+1}$, the smallest positive difference that can affect rounding. Then

$u \oplus v = \text{round}(2u + \delta) = 2u \quad \text{or} \quad 2u + b^{e-p},$

depending on whether rounding goes down or up. Dividing by 2,

$m = u \quad \text{or} \quad u + \tfrac12 b^{e-p}.$

In this case, $m$ may equal $u$, which is still within the interval $[u, v]$, but if $v - u$ is smaller than half an ulp, rounding could produce $m > v$ in extreme underflow situations. Hence the computed midpoint does not always strictly satisfy $u \le m \le v$.

Counterexample. Consider 2-digit decimal floating point arithmetic ($p = 2$, $b = 10$) and let

$u = 0.10, \quad v = 0.11.$

Then

$u \oplus v = \text{round}(0.21) = 0.21,$

so

$m = 0.21 \oslash 2 = \text{round}(0.105) = 0.11.$

Here $m = 0.11 > v$, showing that the computed midpoint can exceed the upper endpoint. This phenomenon occurs whenever the sum $u \oplus v$ rounds up and the interval length is less than one ulp of $u \oplus v$.

Conclusion. The computed midpoint of an interval does not always lie between the endpoints. Exact inclusion requires that the difference $v - u$ be large relative to the rounding unit of $u \oplus v$; otherwise, floating point rounding can place the midpoint slightly outside the interval.

This completes the proof.

∎