TAOCP 4.4 Exercise 5
**5.
Exercise 5. [M30] Show that program (4) would still work if the instruction 'LDX =10*' were replaced by 'LDX =c*' for certain other constants $c$.
Verified: no
Solve time: 10m49s
Exercise 4.4.5 [M30]
5. Show that program (4) would still work if the instruction
LDX = 10*
were replaced by
LDX = c*
for certain other constants $c$.
Solution
Program (4) is the digit-generation procedure of Method 2a. Let the radix of the output notation be $m$. In the published program $m=10$, and the instruction
LDX = 10*
loads the radix into register $X$.
The essential step of the algorithm is repeated multiplication of the current fractional quantity by the radix. If the current fraction is $x$, with $0\le x<1$, the next output digit is
$$ d=\lfloor mx\rfloor , $$
and the new fraction is
$$ x' = mx-d. $$
The correctness proof of Method 2a uses only the fact that the multiplier equals the radix in which the digits are being produced. Nothing in the argument depends on any special property of the number $10$.
Suppose that the instruction is replaced by
LDX = c*
for some positive integer $c$. Then each iteration computes
$$ d=\lfloor cx\rfloor , \qquad x' = cx-d . $$
Since $0\le x<1$,
$$ 0\le cx < c, $$
hence
$$ 0\le d\le c-1, $$
and therefore
$$ 0\le x' <1. $$
Thus the invariant required by Method 2a is preserved. The digits produced are precisely the digits of the radix-$c$ expansion, because at each step the algorithm performs the standard radix-conversion transformation
$$ x=\frac{d}{c}+\frac{x'}{c}. $$
Iterating gives
$$ x = \frac{d_1}{c} + \frac{d_2}{c^2} + \frac{d_3}{c^3} +\cdots , $$
with
$$ 0\le d_i < c. $$
Hence the program remains correct when $10$ is replaced by $c$; it simply converts to radix $c$ instead of radix $10$.
The only restriction is that the machine arithmetic must be able to carry out the multiplication by $c$ without violating the assumptions under which program (4) was derived. In MIX this means that $c$ must be representable as a machine constant and that the product occurring in the multiplication step must fit within the prescribed register pair exactly as in the original proof.
Therefore the mathematically relevant condition is simply
$$ c\ge 2. $$
For every radix $c\ge 2$ for which the machine operations remain valid, replacing
LDX = 10*
by
LDX = c*
produces the radix-$c$ expansion by exactly the same argument that proves correctness for radix $10$.
$$ \boxed{\text{Program (4) works for any radix } c\ge 2 \text{ (subject to the machine's size limitations).}} $$
∎