TAOCP 4.5.2 Exercise 6

Section 4.5.2: The Greatest Common Divisor

Exercise 6. [M22] Given that $u$ and $v$ are random positive integers, find the mean and the standard deviation of the quantity $A$ that enters into the timing of Program B. (This is the number of right shifts applied to both $u$ and $v$ during the preparatory phase.)

Verified: yes
Solve time: 4m59s

Solution

Let $u$ and $v$ be random positive integers. In Program B (Section 4.5.2), the preparatory phase begins by factoring out all powers of $2$ common to $u$ and $v$. That is, we repeatedly perform right shifts of both $u$ and $v$ until at least one of them becomes odd. Let $A$ denote the total number of right shifts applied in this phase. Then $A$ equals the exponent of $2$ in $\gcd(u, v)$, because after $A$ shifts, the resulting integers $u', v'$ satisfy $u', v' \ge 0$, and at least one of them is odd, so $2^A \mid u, v$ and $2^{A+1} \nmid \gcd(u, v)$.

We model $u$ and $v$ as independent, uniformly distributed positive integers. The probability that a randomly chosen positive integer is divisible by $2^a$ but not by $2^{a+1}$ is exactly $2^{-(a+1)}$ for $a \ge 0$, because the $2$-adic valuation $\nu_2(n)$ is geometrically distributed:

$\Pr[\nu_2(n) = a] = 2^{-(a+1)}.$

Since $u$ and $v$ are independent, the $2$-adic valuation of their greatest common divisor satisfies

$\Pr[A = a] = \Pr[\nu_2(u) \ge a \text{ and } \nu_2(v) \ge a, \text{ but not both } \ge a+1] = \Pr[\nu_2(u) \ge a]\Pr[\nu_2(v) \ge a] - \Pr[\nu_2(u) \ge a+1]\Pr[\nu_2(v) \ge a+1].$

We compute each term:

$\Pr[\nu_2(u) \ge a] = \sum_{k=a}^{\infty} 2^{-(k+1)} = 2^{-a},$

and similarly for $v$. Therefore,

$\Pr[A = a] = 2^{-2a} - 2^{-2(a+1)} = 2^{-2a} - 2^{-2a-2} = \frac{3}{4} \cdot 4^{-a}.$

Hence $A$ has a geometric distribution with success parameter $p = 3/4$, expressed as

$\Pr[A = a] = \frac{3}{4} \cdot 4^{-a}, \quad a = 0,1,2,\dots.$

The mean of a geometrically distributed random variable with probability mass function $\Pr[X = a] = (1-p)^{a} p$ for $a \ge 0$ is $(1-p)/p$. Here, $(1-p)/p = (1/4)/(3/4) = 1/3$. Therefore, the expected number of right shifts is

$\mathbb{E}[A] = \frac{1}{3}.$

To compute the variance, recall that for such a geometric distribution,

$\operatorname{Var}[A] = \frac{1-p}{p^2} = \frac{1/4}{(3/4)^2} = \frac{1/4}{9/16} = \frac{4}{9}.$

Thus, the standard deviation is

$\sigma_A = \sqrt{\operatorname{Var}[A]} = \frac{2}{3}.$

This completes the derivation. The preparatory right shifts applied to random integers have mean $1/3$ and standard deviation $2/3$.

$\boxed{\mathbb{E}[A] = \frac{1}{3}, \quad \sigma_A = \frac{2}{3}} \quad \text{for random positive integers } u, v.$

∎