TAOCP 3.1 Exercise 4
Step K11 of Algorithm K is the normalization step.
Exercise 4. [20] (a) Why can't the value of $X$ be zero when step K11 of Algorithm K is performed? What would be wrong with the algorithm if $X$ could be zero? (b) Use Table 1 to deduce what happens when Algorithm K is applied repeatedly with the starting value $X = 3830951656$.
Verified: yes
Solve time: 3m22s
Solution
(a)
Step K11 of Algorithm K is the normalization step. Its purpose is to ensure that the current value of $X$ has ten digits, allowing leading zeros if necessary. Operationally, K11 repeatedly multiplies $X$ by $10$ until
$$ X \ge 10^9. $$
If $X>0$, this process terminates after finitely many multiplications.
However, if $X=0$ when K11 is entered, multiplication by $10$ leaves the value unchanged:
$$ 0 \mapsto 0 \mapsto 0 \mapsto \cdots . $$
Hence the test used in K11 is never satisfied. The algorithm would remain in step K11 forever and would never proceed to K12. Thus $X=0$ is impossible when K11 is performed; otherwise Algorithm K would fail to terminate. The difficulty is not merely that $0$ would be a fixed point, but that the control structure of K11 itself would enter an infinite loop.
(b)
Table 1 exhibits a complete cycle of Algorithm K. In the table one finds the successive values
$$ 3830951656 \stackrel{\mathrm{K12}}{\longrightarrow} 1905867781 \stackrel{\mathrm{K12}}{\longrightarrow} 3319967479 \stackrel{\mathrm{K6,K7,K8,K9,K10,K11,K12}}{\longrightarrow} 1226919902 $$
and later
$$ 1226919902 \stackrel{\mathrm{K5,K6,K7,K8,K9,K10,K11,K12}}{\longrightarrow} 5870802097, $$
$$ 5870802097 \stackrel{\mathrm{K11,K12}}{\longrightarrow} 3172562687, $$
$$ 3172562687 \stackrel{\mathrm{K4,K5,K6,K7,K8,K9,K10,K11,K12}}{\longrightarrow} 6065038420. $$
Finally, the table begins with the value
$$ 6065038420 $$
and shows that one complete execution of Algorithm K returns to
$$ 6065038420. $$
Thus $6065038420$ is a fixed point of the algorithm.
Since the starting value $3830951656$ appears in this chain and the chain eventually reaches $6065038420$, repeated application of Algorithm K yields
$$ 3830951656 \longrightarrow 1905867781 \longrightarrow 3319967479 \longrightarrow 1226919902 \longrightarrow 5870802097 \longrightarrow 3172562687 \longrightarrow 6065038420 \longrightarrow 6065038420 \longrightarrow \cdots . $$
Therefore, when Algorithm K is repeatedly applied with initial value
$$ X=3830951656, $$
the sequence eventually reaches the fixed point
$$ 6065038420, $$
after which every subsequent value is again $6065038420$. This is exactly the phenomenon illustrated by Table 1, entitled “A colossal coincidence: the number $6065038420$ is transformed into itself by Algorithm K.”