TAOCP 4.5.2 Exercise 20

Let $M=2^{n'-1}.$ The odd integers in the interval $2^{n'}\le u,v<2^{n'+1}$ are $u=2^{n'}+(2a+1),\qquad v=2^{n'}+(2b+1),$ with $0\le a,b<M$.

taocpmathematicsalgorithmsvolume-2

Section 4.5.2: The Greatest Common Divisor

Exercise 20. [**] [M37] Let $u$ and $v$ be odd integers, independently and uniformly distributed in the ranges $2^{n'} \le u < 2^{n'+1}$, $2^{n'} \le v < 2^{n'+1}$. What is the exact probability that a single subtract-and-shift cycle in Algorithm B reduces $u$ and $v$ to the ranges $2^{n'} \le u < 2^{n'+1}$, $2^{n'} \le v < 2^{n'+1}$, and $n$?

Verified: yes
Solve time: 2m18s

Let

$M=2^{n'-1}.$

The odd integers in the interval $2^{n'}\le u,v<2^{n'+1}$ are

$u=2^{n'}+(2a+1),\qquad v=2^{n'}+(2b+1),$

with $0\le a,b<M$. In one subtract-and-shift cycle of Algorithm B, the larger of $u,v$ is replaced by

$w=\operatorname{oddpart}(|a-b|),$

where $\operatorname{oddpart}(k)=k/2^{\nu_2(k)}$. Thus $w$ is an odd integer satisfying $1\le w<2^{n'-1}$, and the new exponent $n$ is determined by

$2^n\le w<2^{n+1},\qquad 0\le n\le n'-2.$

For a fixed odd $m$, the values $|a-b|=m2^t<M$ contribute

$2(M-m2^t)$

ordered pairs $(a,b)$. Hence the number of ordered pairs producing $\operatorname{oddpart}(|a-b|)=m$ is

$2\sum_{t=0}^{,n'-2-\lfloor\lg m\rfloor}(M-m2^t).$

Summing over all odd $m$ with $2^n\le m<2^{n+1}$ gives

$$= 2!!\sum_{\substack{2^n\le m<2^{n+1}\ m\ \mathrm{odd}}} \left((n'-1-n)M-m\bigl(2^{,n'-1-n}-1\bigr)\right).$$

Since there are $2^{n-1}$ such odd $m$ for $n\ge1$, and their sum is

$3\cdot2^{2n-2}$, this simplifies to

$$ N_n = 2^{,n'+n-2}(2n'-2n-5)+3\cdot2^{,2n-1}, \qquad 1\le n\le n'-2. $$

For $n=0$, only $m=1$ occurs, giving

$$ N_0 = 2\bigl((n'-1)M-(2^{,n'-1}-1)\bigr) = (n'-2)2^{,n'}+2. $$

Since the total number of ordered pairs is $M^2=2^{2n'-2}$, the exact probability that one subtract-and-shift cycle yields a result in the range

$2^n\le w<2^{n+1}$

is

$$ \boxed{ P_0=\frac{(n'-2)2^{,n'}+2}{2^{,2n'-2}} } $$

and, for $1\le n\le n'-2$,

$$ \boxed{ P_n= \frac{ 2^{,n'+n-2}(2n'-2n-5)+3\cdot2^{,2n-1} } {2^{,2n'-2}} }. $$

These probabilities sum to $1-2^{-(n'-1)}$; the missing probability $2^{-(n'-1)}$ corresponds to the case $u=v$, when Algorithm B terminates immediately. ∎