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.

C++
 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)
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用