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)