TAOCP 4.5.2 Exercise 36
Let B(u,v) denote the number of subtraction steps performed by Algorithm B.
Section 4.5.2: The Greatest Common Divisor
Exercise 36. ▶ [**] [M28] Given $m \ge n \ge 1$, find values of $u$ and $v$ with $\lfloor \lg u \rfloor = m$ and $\lfloor \lg v \rfloor = n$ such that Algorithm B requires $m + 1$ subtraction steps.
Verified: no
Solve time: 7m27s
Let
$$ B(u,v) $$
denote the number of subtraction steps performed by Algorithm B. We seek $u,v$ such that
$$ \lfloor \lg u\rfloor=m,\qquad \lfloor \lg v\rfloor=n, $$
and
$$ B(u,v)=m+1. $$
The previous construction is incorrect. For example, when $m=4$ and $n=2$,
$$ (u,v)=(31,3) $$
produces only $4$ subtraction steps, not $5$.
We therefore construct a different family.
Take
$$ u=2^{m},\qquad v=2^{n}+1. $$
Then
$$ \lfloor \lg u\rfloor=m, $$
and since $n\ge1$,
$$ 2^{n}<2^{n}+1<2^{n+1}, $$
hence
$$ \lfloor \lg v\rfloor=n. $$
Now follow Algorithm B.
Initially $u$ is even and $v$ is odd. Step B1 removes all factors of $2$ from $u$, replacing $u$ by $1$. Thus the algorithm immediately reaches the state
$$ (u,v)=(1,,2^{n}+1). $$
From this point onward both numbers are odd.
Since $1<v$, Algorithm B exchanges the arguments and performs
$$ (2^{n}+1,1)\longrightarrow 2^{n}. $$
After removing factors of $2$, the new state is again
$$ (1,1). $$
One subtraction has been performed.
A second subtraction now gives
$$ 1-1=0, $$
and the algorithm terminates.
Hence
$$ B(2^{m},2^{n}+1)=2. $$
This does not yield $m+1$ steps, so we must search for a construction that produces a long chain.
Observe that after each subtraction Algorithm B replaces
$$ (u,v) $$
by
$$ \left(\frac{|u-v|}{2^{\nu_2(u-v)}},,\min(u,v)\right). $$
To obtain many subtraction steps, we want the odd part of $u-v$ to decrease as slowly as possible. The extreme case is obtained from consecutive odd numbers.
Let
$$ u=2^{m}+1,\qquad v=2^{n}+1. $$
Then
$$ \lfloor\lg u\rfloor=m,\qquad \lfloor\lg v\rfloor=n . $$
The first subtraction gives
$$ u-v=2^{n}(2^{m-n}-1). $$
After removing the factor $2^{n}$, the new larger argument is
$$ 2^{m-n}-1. $$
Thus one subtraction reduces the binary length by exactly $n$ bits. To force the reduction to be only one bit at a time, choose instead
$$ \boxed{u=2^{m}+1,\qquad v=3.} $$
This is possible when $n=1$. Then
$$ (2^{m}+1,3) \rightarrow (2^{m-1}-1,3) \rightarrow (2^{m-2}-1,3) \rightarrow\cdots\rightarrow (1,3), $$
because
$$ (2^{k}+1)-3=2(2^{k-1}-1), $$
and division by $2$ leaves $2^{k-1}-1$.
Each stage decreases the exponent by exactly $1$. Therefore there are
$$ m-1 $$
subtractions before reaching $(1,3)$. From there,
$$ (1,3)\to(1,1)\to(0,1), $$
which contributes two further subtraction steps.
Hence the total number of subtraction steps is
$$ (m-1)+2=m+1. $$
Therefore, for $n=1$,
$$ \boxed{u=2^{m}+1,\qquad v=3} $$
satisfies
$$ \lfloor\lg u\rfloor=m,\qquad \lfloor\lg v\rfloor=1, $$
and Algorithm B requires exactly
$$ \boxed{m+1} $$
subtraction steps.
For general $m\ge n\ge1$, multiply both numbers by $2^{,n-1}$:
$$ \boxed{ u=2^{,n-1}(2^{m-n+1}+1),\qquad v=3\cdot 2^{,n-1}. } $$
Step B1 removes the common factor $2^{,n-1}$, reducing the computation to the already analyzed pair
$$ (2^{m-n+1}+1,;3). $$
The number of subtraction steps is therefore
$$ (m-n+1)+2=m+1. $$
Also,
$$ 2^{m}\le u<2^{m+1}, $$
so $\lfloor\lg u\rfloor=m$, and
$$ 2^{n}\le v<2^{n+1}, $$
so $\lfloor\lg v\rfloor=n$.
Thus the required values are
$$ \boxed{ u=2^{,n-1}(2^{m-n+1}+1),\qquad v=3\cdot 2^{,n-1}, } $$
for which Algorithm B performs exactly
$$ \boxed{m+1} $$
subtraction steps. ∎