Question

2gcd(a/2, b/2) if a, b are both even ged(a, b/2)if a is odd, b is even ged(a,bged(a/2, b) if a is even, b is odd gcd(a -b)/2, b) if a, b are both odd (b) Give an efficient divide-and-conquer algorithm for greatest common divisor, based on the above. (c) Express the running time of your algorithm for the case where a and b are both n-bit numbers. Recall that dividing by two results in the removal of one bit from a value. You will want to express this as T(2n)- (d) Find a closed form for the recurrence relation you gave in the previous part. Note that this won't work for using the master theorem.

Answer 1

b.

The recursive divide-and-conquer algorithm for gcd is given as
procedure gcd(a,b)
Input: Two n-bit integers a,b
Output: GCD of a and b
if a = b:
return a
else if (a is even ∧ b is even):
return 2 * gcd( a/2,b/2)
else if (a is odd ∧ b is even):
return gcd(a, b/2)
else if (a is even ∧ b is odd):
return gcd(a/2, b)
else if (a is odd ∧ b is odd ∧ a > b):
return gcd( (a−b)/2,b)
else if (a is odd ∧ b is odd ∧ a < b):
return gcd(a,(b−a)/2)

c and d.

Assume that a and b are n-bit numbers. Size of a and b is 2n bits. Out of 4 if conditions, every one except the case when a is odd and b is even, decreases the size of a and b to 2n − 2 bits whereas that case decreases it to 2n − 1 bits. Each of the operations is constant time operation as we are dividing or multiplying the numbers by 2. For two cases subtraction of two n-bit numbers are involved which is c·n where n is the number of bits of the operand. Therefore in the worst case:

T(2n) = T(2n − 1) + cn
T(2n − 1) = T(2n − 2) + cn
T(2n − 2) = T(2n − 3) + c(n − 1) both operands are n-1 bits
T(2n − 3) = T(2n − 4) + c(n − 1)
...
T(2) = T(1) + c
Using substitution, we can obtain T(2n) as
T(2n) = 2c ·summation(i) from i=1 to i(12)
which is O(n^2).

Compared to the O(n^3 ) running time of Euclid’s the divide-and-conquer algorithm which is slower