TAOCP 4.2.2 Exercise 1

We are asked to prove identity (7): $u \ominus v = -(v \ominus u)$ using only identities (2) through (6): \begin{aligned} &(2) && u \oplus v = v \oplus u, \\

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.2.2: Accuracy of Floating Point Arithmetic

Exercise 1. [M18] Prove that identity (7) is a consequence of (2) through (6).

Verified: yes
Solve time: 1m40s

Solution

We are asked to prove identity (7):

$u \ominus v = -(v \ominus u)$

using only identities (2) through (6):

$$ \begin{aligned} &(2) && u \oplus v = v \oplus u, \ &(3) && u \ominus v = u \oplus (-v), \ &(4) && -(u \oplus v) = -u \oplus -v, \ &(5) && u \oplus v = 0 \iff v = -u, \ &(6) && u \oplus 0 = u. \end{aligned} $$

We proceed step by step, applying these identities.

Starting from the left-hand side of (7) and using (3), we have

$$ u \ominus v = u \oplus (-v). $$

We now rewrite $u \oplus (-v)$ by using (4) in a rearranged form. Identity (4) states $-(a \oplus b) = -a \oplus -b$, which implies

$$ a \oplus b = -(-a \oplus -b). $$

Applying this with $a = -v$ and $b = u$, we obtain

$$ u \oplus (-v) = -((-(-v)) \oplus (-u)) = - (v \oplus (-u)). $$

Next, we use (3) in the form $x \ominus y = x \oplus (-y)$ with $x = v$ and $y = u$, giving

$$ v \ominus u = v \oplus (-u). $$

Combining the previous steps, we find

$$ u \ominus v = - (v \oplus (-u)) = - (v \ominus u). $$

This is exactly identity (7).

This completes the proof.

∎