TAOCP 4.2.1 Exercise 5
Let the quantity actually stored for exponent $e$ be denoted by $F_e$.
Section 4.2.1: Single-Precision Calculations
Exercise 5. [24] Let us say that $x \sim y$ (with respect to a given radix $b$) if $x$ and $y$ are real numbers satisfying the following conditions:
$$\lfloor x/b \rfloor = \lfloor y/b \rfloor;$$
$$x \bmod b = 0 \iff y \bmod b = 0;$$
$$0 < x \bmod b < \tfrac{1}{2}b \iff 0 < y \bmod b < \tfrac{1}{2}b;$$
$$x \bmod b = \tfrac{1}{2}b \iff y \bmod b = \tfrac{1}{2}b;$$
$$\tfrac{1}{2}b < x \bmod b < b \iff \tfrac{1}{2}b < y \bmod b < b.$$
Prove that if $f_e$ is replaced by $b^{p-2}F_e$, the result of that algorithm will be unchanged. (If $F_e$ is an integer and $b$ is even, this operation essentially truncates $f_e$ to $p + 2$ places while remembering whether any nonzero digits have been dropped, thereby minimizing the length of register that is needed for the addition in step A6.)
Verified: yes
Solve time: 5m01s
Solution
Let the quantity actually stored for exponent $e$ be denoted by $F_e$. The point of the exercise is that the algorithm does not need the exact value of $f_e$; it needs only enough information to determine the outcome of the rounding test performed in Algorithm N.
The relation $x\sim y$ is designed precisely to capture the information relevant to that rounding test. Recall that
$$ x\sim y $$
means:
- $\lfloor x/b\rfloor=\lfloor y/b\rfloor$;
- $x\bmod b$ and $y\bmod b$ are simultaneously $0$;
- or simultaneously in $(0,\tfrac12 b)$;
- or simultaneously equal to $\tfrac12 b$;
- or simultaneously in $(\tfrac12 b,b)$.
Thus two numbers are equivalent when they have the same integer part upon division by $b$, and when their remainders modulo $b$ fall into the same one of the four classes that determine the rounding decision.
We shall show that every operation of Algorithm A depends only on the $\sim$-class of the quantities involved. Consequently, replacing $f_e$ by any representative of the same $\sim$-class leaves the algorithm unchanged.
1. The stored quantity $F_e$
The exercise proposes replacing $f_e$ by
$$ b^{p-2}F_e. $$
As Knuth remarks, $F_e$ is obtained by truncating $f_e$ to $p+2$ places and remembering whether any discarded digit was nonzero.
Therefore $b^{p-2}F_e$ is not the exact scaled fraction $b^{p-2}f_e$; rather, it is a representative having exactly the same:
- quotient upon division by $b$;
- status of the remainder modulo $b$ as being
$0$, $<b/2$, $=b/2$, or $>b/2$.
Hence
$$ b^{p-2}F_e \sim b^{p-2}f_e . $$
The proof reduces to showing that Algorithm A uses $b^{p-2}f_e$ only through its $\sim$-class.
2. Addition preserves $\sim$
Suppose
$$ x\sim x', \qquad y\sim y'. $$
Write
$$ x=qb+r,\qquad x'=qb+r', $$
with
$$ 0\le r,r'<b, $$
and similarly
$$ y=pb+s,\qquad y'=pb+s'. $$
Since $x\sim x'$, the remainders $r$ and $r'$ belong to the same one of the four classes
$$ {0},\quad (0,\tfrac12 b),\quad {\tfrac12 b},\quad (\tfrac12 b,b). $$
The same is true of $s$ and $s'$.
Now consider
$$ x+y=(q+p)b+(r+s). $$
The quotient $\lfloor(x+y)/b\rfloor$ is determined by $q+p$ together with whether $r+s<b$ or $r+s\ge b$.
Likewise, the class of
$$ (x+y)\bmod b $$
is determined solely by the position of $r+s$ relative to
$$ 0,\quad \tfrac12 b,\quad b,\quad \tfrac32 b,\quad 2b. $$
Because the four classes above record exactly on which side of $0$, $b/2$, and $b$ each remainder lies, the corresponding sums $r+s$ and $r'+s'$ necessarily fall into the same interval determined by these critical values. Hence
$$ x+y\sim x'+y'. $$
Therefore addition is compatible with $\sim$.
3. Shifts by powers of $b$ preserve $\sim$
Algorithm A aligns exponents by dividing one fraction by a power of $b$.
Multiplication or division by $b^k$ merely shifts radix-point positions. If
$$ x\sim y, $$
then
$$ \frac{x}{b^k}\sim \frac{y}{b^k}, $$
because the quotient upon division by $b$ and the classification of the remainder modulo $b$ are transformed identically for both numbers.
Hence the exponent-alignment operations of steps A4-A5 preserve $\sim$.
4. Normalization and rounding depend only on $\sim$
After the addition step, Algorithm N examines the digit immediately beyond the retained precision.
In the scaled formulation, this examination is equivalent to looking at a number $z$ and determining:
- $\lfloor z/b\rfloor$;
- whether $z\bmod b$ is
$0$,
$< b/2$,
$= b/2$,
or
$> b/2$.
But these are exactly the data encoded by the equivalence relation $\sim$.
Therefore, if
$$ z\sim z', $$
Algorithm N makes the same rounding decision for $z$ and $z'$. The carry produced by rounding is the same in both cases, so the resulting normalized fraction and exponent are identical.
5. Induction through the algorithm
Initially, for every exponent $e$,
$$ b^{p-2}F_e \sim b^{p-2}f_e. $$
Steps A4-A5 preserve $\sim$ because shifts by powers of $b$ preserve $\sim$.
Step A6 preserves $\sim$ because addition preserves $\sim$.
Step A7 and Algorithm N depend only on the $\sim$-class of their arguments.
Hence every quantity computed using the modified representation remains $\sim$-equivalent to the quantity that would have been computed using the exact fractions. Since the final normalization and rounding use only the information contained in the $\sim$-class, both versions of the algorithm produce exactly the same result.
Therefore replacing $f_e$ by $b^{p-2}F_e$ leaves Algorithm A unchanged.
$$ \boxed{\text{The modified algorithm yields exactly the same floating-point result.}} $$
∎