TAOCP 4.5.2 Exercise 8
Let the notation be that of Knuth's analysis of Program B.
Section 4.5.2: The Greatest Common Divisor
Exercise 8. ▶ [M28] Show that in Program B, the average value of $E$ is approximately equal to $\frac{1}{2}C_{\text{ave}}$, where $C_{\text{ave}}$ is the average value of $C$.
Verified: yes
Solve time: 3m34s
Solution
Let the notation be that of Knuth's analysis of Program B.
At each execution of the subtraction step, the algorithm forms
$$ t=|u-v|, $$
where $u$ and $v$ are odd. Hence $t$ is even, and we may write
$$ t=2^{e}w, \qquad w \text{ odd}, $$
with $e=\nu_2(t)\ge 1$.
In Program B, one factor $2$ must always be removed after each subtraction, because $t$ is even. Additional factors of $2$ beyond the first contribute to the parameter $E$. Therefore, for a subtraction step having valuation $e$,
$$ \text{contribution to }C = e, \qquad \text{contribution to }E = e-1. $$
If the execution contains subtraction steps indexed by $j$, with corresponding valuations $e_j$, then by the definitions of the parameters,
$$ C=\sum_j e_j, \qquad E=\sum_j (e_j-1). $$
Thus $C$ and $E$ are sums over exactly the same collection of subtraction steps.
To determine the average relation between $E$ and $C$, we need the distribution of
$$ e=\nu_2(u-v). $$
Since $u$ and $v$ are odd, their residue classes modulo $2^k$ are approximately equidistributed among the $2^{k-1}$ odd residue classes. The condition
$$ e\ge k $$
is equivalent to
$$ u\equiv v \pmod{2^k}. $$
For a fixed odd residue class of $u$ modulo $2^k$, exactly one odd residue class of $v$ modulo $2^k$ satisfies this congruence. Hence
$$ \Pr(e\ge k)\approx \frac1{2^{k-1}}, \qquad k\ge1. $$
Therefore
$$ \Pr(e=k) =\Pr(e\ge k)-\Pr(e\ge k+1) \approx \frac1{2^{k-1}}-\frac1{2^k} =\frac1{2^k}, \qquad k\ge1. $$
The mean valuation is
$$ \mathbf E[e] =\sum_{k\ge1} k,2^{-k}. $$
Using
$$ \sum_{k\ge1} kx^k=\frac{x}{(1-x)^2}, $$
with $x=\frac12$, we obtain
$$ \mathbf E[e] =2. $$
Hence
$$ \mathbf E[e-1] =1 =\frac12,\mathbf E[e]. $$
Now let $N$ denote the number of subtraction steps occurring in an execution. Since $C$ and $E$ are sums over the same steps,
$$ C=\sum_{j=1}^{N} e_j, \qquad E=\sum_{j=1}^{N} (e_j-1). $$
Taking averages over all executions and using linearity of expectation,
$$ C_{\mathrm{ave}} =\mathbf E!\left[\sum_{j=1}^{N} e_j\right], \qquad E_{\mathrm{ave}} =\mathbf E!\left[\sum_{j=1}^{N} (e_j-1)\right]. $$
For each subtraction step, the average contribution to $E$ is one-half the average contribution to $C$, because
$$ \mathbf E[e-1] =\frac12,\mathbf E[e]. $$
Since the same set of subtraction steps contributes to both sums, the common factor arising from the average number of subtraction steps cancels, giving
$$ E_{\mathrm{ave}} \approx \frac{\mathbf E[e-1]}{\mathbf E[e]} ,C_{\mathrm{ave}} = \frac12,C_{\mathrm{ave}}. $$
Therefore
$$ \boxed{E_{\mathrm{ave}}\approx \frac12,C_{\mathrm{ave}}}. $$
This is the required result.