TAOCP 4.5.2 Exercise 23

Let F_n(x)=\Pr\!

taocpmathematicsalgorithmsvolume-2

Section 4.5.2: The Greatest Common Divisor

Exercise 23. ▶ [**] [M20] What is the probability that $v/u \le x$ after $n$ subtract-and-shift cycles of Algorithm B, when the algorithm begins with large random integers? (Here $x$ is any real number $\ge 0$; we do not assume that $u \ge v$.)

Verified: yes
Solve time: 2m21s

Let

$$ F_n(x)=\Pr!\left(\frac vu\le x \text{ after } n \text{ subtract-and-shift cycles of Algorithm B}\right), \qquad x\ge0. $$

We assume that the algorithm starts with large random integers $u,v$, and we seek an exact recurrence for $F_n$.

A subtract-and-shift cycle acts on the ratio $t=v/u$. Since Algorithm B is symmetric in $u$ and $v$, it is convenient to describe the ratio after one cycle.

If $t\ge1$, write

$$ v-u=2^k w,\qquad w\ \text{odd},\ k\ge0. $$

For large random integers, the exponent $k=\nu_2(v-u)$ has the geometric distribution

$$ \Pr(k=m)=2^{-(m+1)},\qquad m\ge0, $$

and is asymptotically independent of the odd part. After the subtraction and removal of factors $2$,

$$ (u,v)\mapsto (u,w), $$

hence

$$ t=\frac vu \longmapsto \frac{t-1}{2^k}. $$

If $0<t<1$, symmetry gives

$$ t\longmapsto \frac1{(1/t-1)/2^k} =\frac{2^k t}{1-t}. $$

Therefore the distribution after one cycle is obtained by averaging over all

$k\ge0$ with weights $2^{-(k+1)}$.

Let $F_n$ be the distribution function after $n$ cycles. Then

$$ F_{n+1}(x) = \sum_{k\ge0}\frac1{2^{k+1}} \Pr!\left(T_{k}(t)\le x\right), $$

where $t$ has distribution $F_n$ and $T_k$ denotes the one-cycle map.

We now compute the event $T_k(t)\le x$.

For $t\ge1$,

$$ \frac{t-1}{2^k}\le x \iff t\le 1+2^k x. $$

For $0<t<1$,

$$ \frac{2^k t}{1-t}\le x \iff t\le \frac{x}{x+2^k}. $$

Hence

$$ \Pr(T_k(t)\le x) = F_n!\left(\frac{x}{x+2^k}\right) + \Bigl( F_n(1+2^k x)-F_n(1) \Bigr). $$

Substituting into the preceding expression yields the fundamental recurrence

$$ \boxed{ F_{n+1}(x) = \sum_{k\ge0}\frac1{2^{k+1}} \left[ F_n!\left(\frac{x}{x+2^k}\right) + F_n(1+2^k x) - F_n(1) \right]. } $$

This formula gives exactly the probability distribution of $v/u$ after $n+1$ subtract-and-shift cycles in terms of the distribution after $n$ cycles.

To complete the solution, we need the initial distribution. For large independent random integers $u$ and $v$,

$$ F_0(x) = \Pr!\left(\frac vu\le x\right). $$

A standard calculation gives

$$ F_0(x)= \begin{cases} \dfrac{x}{2}, & 0\le x\le1,\[1ex] 1-\dfrac1{2x}, & x\ge1. \end{cases} $$

Therefore the required probability after $n$ subtract-and-shift cycles is

$$ \boxed{ F_n(x), } $$

where $F_0$ is the function above and $F_n$ is obtained by iterating

$$ F_{n+1}(x) = \sum_{k\ge0}\frac1{2^{k+1}} \left[ F_n!\left(\frac{x}{x+2^k}\right) + F_n(1+2^k x) - F_n(1) \right]. $$

This is the finite-$n$ distribution sought in the exercise. As $n\to\infty$, the functions $F_n$ converge to the invariant distribution of the binary Euclidean transformation, but the probability after exactly $n$ cycles is given by the recurrence above. ∎