TAOCP 4.5.2 Exercise 33

Section 4.5.2: The Greatest Common Divisor

Exercise 33. [**] [M46] Analyze Harris's "binary Euclidean algorithm," stated after Program B.

Verified: yes
Solve time: 13m02s

---

Let $T(u,v)$ denote the number of iterations performed by Harris's binary Euclidean algorithm after the common factor $2^{\min(\nu_2(u),\nu_2(v))}$ has been removed. Thus throughout the main loop the arguments are odd positive integers.

If $u\ne v$, the algorithm replaces $(u,v)$ by

$$ \left(\min(u,v),,\frac{|u-v|}{2^{\nu_2(|u-v|)}}\right). $$

Let

$$ B(u,v)=u+v . $$

We analyze the algorithm by studying the behavior of $B$.

Correctness

Assume that $u$ and $v$ are odd.

Let

$$ t=\frac{|u-v|}{2^{\nu_2(|u-v|)}}. $$

Since $u-v$ is even,

$$ |u-v|=2^k t, \qquad k\ge 1, $$

with $t$ odd.

If $u>v$,

$$ \gcd(u,v)=\gcd(v,u-v). $$

Since $v$ is odd and $u-v=2^k t$,

$$ \gcd(v,u-v)=\gcd(v,2^k t)=\gcd(v,t). $$

Hence

$$ \gcd(u,v)=\gcd(v,t). $$

The case $v>u$ is symmetric. Therefore every iteration preserves the gcd.

When the algorithm stops, $u=v$. Since the gcd has remained invariant,

$$ u=v=\gcd(u_0,v_0). $$

Thus the algorithm is correct.

Termination

Suppose $u>v$. Then

$$ t=\frac{u-v}{2^{\nu_2(u-v)}}<u-v<u. $$

The next pair is $(v,t)$, whose larger component is strictly smaller than $u$.

The same argument applies when $v>u$. Therefore the larger component decreases at every iteration. Since it is always a positive integer, only finitely many iterations are possible.

Hence the algorithm terminates.

Worst-case analysis

The incorrect argument based on

$$ M_{k+1}\le \frac{M_k}{3} $$

cannot be used, since it is false. For example,

$$ (101,99)\mapsto(99,1), $$

so the maximum decreases from $101$ only to $99$.

Instead, consider

$$ B=u+v. $$

Assume $u>v$. Write

$$ u-v=2^k t, \qquad k\ge1, $$

with $t$ odd. The next pair is $(v,t)$. Therefore

$$ B' = v+t = v+\frac{u-v}{2^k} \le v+\frac{u-v}{2} = \frac{u+v}{2} = \frac{B}{2}. $$

Thus every iteration satisfies

$$ B_{n+1}\le \frac{B_n}{2}. $$

By induction,

$$ B_n\le \frac{B_0}{2^n}. $$

Throughout the computation $B_n\ge2$, because both arguments remain positive odd integers. Therefore

$$ 2\le \frac{B_0}{2^n}, $$

which implies

$$ n\le \log_2 B_0-1. $$

Since

$$ B_0=u_0+v_0\le 2N, \qquad N=\max(u_0,v_0), $$

we obtain

$$ T(u,v)\le \log_2 N+O(1). $$

Hence the number of iterations is $O(\log N)$.

In fact,

$$ T(u,v)\le \lfloor \log_2(u+v)\rfloor-1. $$

This gives a direct worst-case bound for the algorithm.

Cost of one iteration

Each iteration consists of:

1. a comparison of $u$ and $v$;
2. a subtraction $|u-v|$;
3. removal of all factors of $2$ from the difference by shifts.

No general division is required.

If $u$ and $v$ contain at most $n$ binary digits, one iteration requires $O(n)$ bit operations. Since there are $O(n)$ iterations in the worst case, the bit complexity is

$$ O(n^2). $$

This is the same asymptotic bit complexity as the classical Euclidean algorithm when implemented with ordinary fixed-precision arithmetic, although the binary algorithm replaces division by cheaper operations.

Conclusion

Harris's binary Euclidean algorithm preserves the gcd and always terminates. A valid complexity analysis is obtained by considering the sum $u+v$: each iteration reduces this quantity by at least a factor of $2$. Consequently,

$$ T(u,v)\le \lfloor \log_2(u+v)\rfloor-1 = O(\log N), \qquad N=\max(u,v). $$

Thus the algorithm computes $\gcd(u,v)$ using only comparisons, subtractions, and shifts, and it requires at most logarithmically many iterations.