TAOCP 4.2.2 Exercise 26

Let $u$, $u'$, $v$, and $v'$ be positive normalized floating point numbers, with $u \sim u' \ (\text{relative error } r), \qquad v \sim v' \ (\text{relative error } s).$ By definition of relative erro...

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.2.2: Accuracy of Floating Point Arithmetic

Exercise 26. [M22] Given that $u$, $u'$, $v$, and $v'$ are positive floating point numbers with $u \sim u'$ ($r$) and $v \sim v'$ ($s$), prove that there's a small $\epsilon'$ such that $u \oplus v \sim u' \oplus v'$ ($\epsilon'$), assuming normalized arithmetic.

Verified: yes
Solve time: 2m15s

Solution

Let $u$, $u'$, $v$, and $v'$ be positive normalized floating point numbers, with

$u \sim u' \ (\text{relative error } r), \qquad v \sim v' \ (\text{relative error } s).$

By definition of relative error (Section 4.2.2), there exist $\delta_u$ and $\delta_v$ with $|\delta_u| \le r$ and $|\delta_v| \le s$ such that

$u' = u(1 + \delta_u), \qquad v' = v(1 + \delta_v).$

Consider the floating point sum $u' \oplus v'$. By equation (17) in Section 4.2.2, the floating point addition of normalized numbers can be written as

$u' \oplus v' = (u' + v')(1 + \delta), \qquad |\delta| \le \epsilon,$

where $\epsilon = \frac{1}{2} b^{1-p}$ is the maximal relative error due to rounding in one addition. Substituting $u' = u(1 + \delta_u)$ and $v' = v(1 + \delta_v)$, we obtain

\begin{align*}

u' \oplus v' &= \big(u(1 + \delta_u) + v(1 + \delta_v)\big)(1 + \delta) \

&= \big(u + v + u \delta_u + v \delta_v\big)(1 + \delta) \

&= (u + v) \Big(1 + \frac{u \delta_u + v \delta_v}{u + v}\Big)(1 + \delta) \

&= (u + v) \big(1 + \delta'\big),

\end{align*}

where we define

$\delta' = \frac{u \delta_u + v \delta_v}{u + v} + \delta + \frac{u \delta_u + v \delta_v}{u + v} \cdot \delta.$

Since $|\delta_u| \le r$, $|\delta_v| \le s$, and $|\delta| \le \epsilon$, we can bound $|\delta'|$ as

\begin{align*}

|\delta'| &\le \frac{u|\delta_u| + v|\delta_v|}{u + v} + |\delta| + \frac{u|\delta_u| + v|\delta_v|}{u + v} \cdot |\delta| \

&\le \frac{u r + v s}{u + v} + \epsilon + \frac{u r + v s}{u + v} \cdot \epsilon.

\end{align*}

Let

$\epsilon' = \frac{u r + v s}{u + v} + \epsilon + \frac{u r + v s}{u + v} \cdot \epsilon.$

Then $u \oplus v \sim u' \oplus v'$ with relative error $\epsilon'$. Note that $\epsilon'$ is small if $r$, $s$, and $\epsilon$ are small, and the expression is valid for all positive normalized $u$ and $v$.

This completes the proof.

∎