# 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.

  1 2 3 4 5 6 7 8 9 10 11 12 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)