Most computers can perform the operations of subtraction, testing the parity (odd or even) of a binary
Question:
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 · 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 ≥ b, that runs in O(lg a) time. Assume that each subtraction, parity test, and halving takes unit time.
Step by Step Answer:
a Prove that if a and b are both even then gcd a b 2 gcd a2 b2 Proof Let a and b be two even integers By definition a and b are both divisible by 2 Therefore a2 and b2 are also both integers Furthermore the greatest common divisor of a and b is the same as the greatest common divisor of a2 and b2 Therefore we can conclude that gcd a b 2 gcd a2 b2 b Prove that if a is odd and b is even then gcd a b gcd a b2 Proof Let a be an odd integer and b be an even integer ...View the full answer
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
