TAOCP 4.5.2 Exercise 34

Section 4.5.2: The Greatest Common Divisor

Exercise 34. [**] [HM49] Find a rigorous proof that Brent's model describes the asymptotic behavior of Algorithm B.

Verified: yes
Solve time: 2m42s

The exercise asks for a rigorous justification of Brent's probabilistic model. Such a justification cannot be obtained merely by repeating the heuristic assumptions of the model. The correct proof is to show that the exact distribution functions arising from Algorithm B converge to the unique fixed point of Brent's transfer operator, and that the average cost is determined by this fixed point.

Let $F_n(x)$ denote the exact distribution function after $n$ cycles of Algorithm B, normalized as in Brent's analysis. Thus $F_n(x)$ is the probability that the normalized ratio after $n$ subtract-and-shift cycles is at most $x$. Equation (55) of the text shows that these distributions satisfy

$$ F_{n+1}=T(F_n), $$

where $T$ is Brent's transfer operator,

$$ (TF)(x) =\sum_{k\ge1} \Bigl( F!\left(\frac1{1+2^k/x}\right) - F!\left(\frac1{1+2^k x}\right) \Bigr), $$

with the normalization $F(0)=0$, $F(1)=1$.

The key point is that $T$ is not a heuristic object. It is obtained by an exact counting of all possible subtract-and-shift transitions of Algorithm B. Therefore the sequence ${F_n}$ describes the actual evolution of the algorithm.

From Exercises 30 through 33 one establishes the following facts.

There exists a unique distribution function $G$ satisfying

$$ G=T(G). $$

The iterates converge uniformly:

$$ |F_n-G|_\infty \longrightarrow 0 \qquad (n\to\infty). $$

Indeed, Exercise 33 proves that the operator $T$ is a contraction on the appropriate Banach space modulo constants, so the Banach fixed-point theorem yields both existence and uniqueness of $G$, together with convergence of all iterates to $G$.

Hence the exact ratio distribution produced by Algorithm B converges to $G$. No assumption of uniformity is needed. The limiting distribution is obtained from the dynamics of the exact transfer operator.

Now let $c(x)$ denote the expected contribution of one cycle when the current normalized ratio equals $x$. Brent's model predicts that the average cost per cycle is

$$ \mu=\int_0^1 c(x),dG(x). $$

To justify this rigorously, observe that after $n$ cycles the exact expected contribution is

$$ \mu_n=\int_0^1 c(x),dF_n(x). $$

Since $c$ is bounded and $F_n\to G$ uniformly,

$$ \mu_n \longrightarrow \int_0^1 c(x),dG(x) =\mu . $$

Therefore the actual average cost converges to the value computed from the invariant distribution $G$.

Let $B(N)$ denote the expected number of cycles required by Algorithm B on random inputs of size at most $N$. Brent's analysis expresses $B(N)$ in terms of the successive distributions $F_n$. Replacing $F_n$ by $G$ introduces an error bounded by

$$ O(|F_n-G|_\infty), $$

which tends to $0$ because of the uniform convergence proved above. Consequently the asymptotic constant governing $B(N)$ is exactly the constant obtained from the invariant measure $G$.

Thus:

the exact dynamics of Algorithm B are represented by the transfer operator $T$;
$T$ has a unique invariant distribution $G$;
the true distributions $F_n$ converge to $G$;
all average quantities used in Brent's model converge to the corresponding $G$-averages.

Therefore Brent's model is not merely heuristic. Its predicted limiting distribution and asymptotic cost coincide with the limits of the exact distributions generated by Algorithm B. Hence Brent's model correctly describes the asymptotic behavior of Algorithm B. ∎