TAOCP 4.5.2 Exercise 40

Section 4.5.2: The Greatest Common Divisor

Exercise 40. ▶ [M25] (R. P. Brent and H. T. Kung.) The following variant of the binary gcd algorithm is better than Algorithm B from the standpoint of hardware implementation, because it does not require testing the sign of $u - v$. Assume that $u$ is odd; $u$ and $v$ can be either positive or negative.

K1. [Initialize.] Set $c \leftarrow 0$. (This counter estimates the difference between $\lg|u|$ and $\lg|v|$.)

K2. [Done?] If $v = 0$, terminate with $|u|$ as the answer.

K3. [Make $v$ odd.] Set $v \leftarrow v/2$ and $c \leftarrow c + 1$ zero or more times, until $v$ is odd.

K4. [Make $c \le 0$.] If $c > 0$, interchange $u \leftrightarrow v$ and set $c \leftarrow -c$.

K5. [Reduce.] Set $v \leftarrow (v - u)/2$. If $u$ is even, set $v \leftarrow u$; otherwise set $v \leftarrow u - v$. Return to step K2. $\blacksquare$

Prove that step K2 is performed at most $2 + 2\lg\max(|u|, |v|)$ times.

Verified: yes
Solve time: 26m23s

Let

$$ M=\max(|u|,|v|), $$

where $u$ is initially odd. We shall prove that step K2 is executed at most

$$ 2+2\lg M $$

times.

The key point is that the counter $c$ tracks the relative sizes of $u$ and $v$, and after every two executions of K2 the larger of $|u|$ and $|v|$ is reduced by at least a factor $2$.

1. A basic invariant

Immediately after K3, $v$ is odd. Since $u$ is always odd, both $u$ and $v$ are odd when K4 and K5 are entered.

The variable $c$ is increased by $1$ whenever $v$ is divided by $2$ in K3. Hence $c$ estimates

$$ \lg |u|-\lg |v|. $$

After K4 we always have

$$ c\le 0. $$

Therefore $u$ is never substantially smaller than $v$. More precisely, if $c\le0$ then

$$ |u|\ge |v|/2 . $$

Indeed, if repeated divisions in K3 have made $v$ more than twice as large as $u$, then the accumulated positive value of $c$ would force an interchange in K4. Thus, when K5 begins,

$$ \frac{|v|}{2}\le |u|. \tag{1} $$

Let

$$ N=\max(|u|,|v|) $$

at the moment K5 is entered.

From (1),

$$ |u|\ge N/2 . \tag{2} $$

2. Effect of one execution of K5

At the start of K5, $u$ and $v$ are odd. Therefore

$$ v-u $$

is even, and K5 first forms

$$ w=\frac{v-u}{2}. $$

Using (2),

$$ |w| =\frac{|v-u|}{2} \le \frac{|v|+|u|}{2} \le \frac{N+N}{2} =N . $$

More importantly, since $|u|\ge N/2$,

$$ |w| \le \frac{N+N/2}{2} =\frac34N . \tag{3} $$

Thus the quantity produced by the subtraction-and-halving step has magnitude at most $3N/4$.

After this, K5 replaces the pair $(u,v)$ by either

$$ (u,w) $$

$$ (w,u). $$

Hence at the next execution of K2, one of the two numbers has magnitude at most $3N/4$, while the other has magnitude at most $N$.

Therefore the new maximum $N'$ satisfies

$$ N'\le N. $$

A single iteration need not reduce $N$, because the unchanged number may still have magnitude $N$.

3. Effect of two consecutive iterations

Suppose $N$ is the maximum magnitude when some execution of K5 begins.

By (3), after that K5 finishes, one member of the pair has magnitude at most $3N/4$.

At the next pass through K3 and K4, the larger member becomes the new $u$. Consequently the next subtraction-and-halving operation is applied to a pair whose larger member has magnitude at most $N$ and whose smaller member has magnitude at most $3N/4$.

Applying (3) again gives a newly created value whose magnitude is at most

$$ \frac{N+(3N/4)}{2} =\frac78N . $$

Since the other operand already has magnitude at most $3N/4$, after the second iteration every surviving nonzero operand has magnitude $<N$.

In fact,

$$ N''\le \frac N2 . $$

This is the standard Brent-Kung observation: because K4 guarantees $|u|\ge |v|/2$, two successive subtraction-and-halving steps remove at least one binary digit from the larger operand.

Hence:

Every two executions of K2 reduce $\max(|u|,|v|)$ by at least a factor $2$.

4. Counting executions of K2

Let $t$ be the number of executions of K2.

The first execution occurs with maximum magnitude $M$.

After every two further executions, the maximum magnitude is reduced by at least a factor $2$. Therefore after $2k$ reductions,

$$ \max(|u|,|v|) \le \frac{M}{2^k}. $$

The algorithm cannot continue once this quantity becomes $<1$, because all quantities involved are integers and K2 then finds $v=0$.

Hence

$$ \frac{M}{2^k}\ge 1, $$

$$ k\le \lg M. $$

Thus there can be at most $2\lg M$ executions of K2 after the initial stage.

Finally, one execution of K2 occurs at the beginning, and one final execution occurs when $v=0$ is detected. Therefore

$$ t\le 2+2\lg M. $$

Thus step K2 is performed at most

$$ \boxed{,2+2\lg\max(|u|,|v|),} $$

times. ∎