# 31-1 Binary gcd algorithm

Most computers can perform the operations of subtraction, testing the parity (odd or even) of a binary integer, and halving more quickly than computing remainders. This problem investigates the binary gcd algorithm, which avoids the remainder computations used in Euclid's algorithm.

a. Prove that if $a$ and $b$ are both even, then $\gcd(a, b) = 2 \cdot \gcd(a / 2, b / 2)$.

b. Prove that if $a$ is odd and $b$ is even, then $\gcd(a, b) = \gcd(a, b / 2)$.

c. Prove that if $a$ and $b$ are both odd, then $\gcd(a, b) = \gcd((a - b) / 2, b)$.

d. Design an efficient binary gcd algorithm for input integers $a$ and $b$, where $a \ge b$, that runs in $O(\lg a)$ time. Assume that each subtraction, parity test, and halving takes unit time.

(Omit!)

d.

BINARY-GCD(a, b)
if a < b
return BINARY-GCD(b, a)
if b == 0
return a
if (a & 1 == 1) and (b & 1 == 1)
return BINARY-GCD((a - b) >> 1, b)
if (a & 1 == 0) and (b & 1 == 0)
return BINARY-GCD(a >> 1, b >> 1) << 1
if a & 1 == 1
return BINARY-GCD(a, b >> 1)
return BINARY-GCD(a >> 1, b)