Exercise 2.

We consider the following algorithm, which computes the gcd of two integer numbers.

 
gcd(a : $\mbox{${\mathbb Z}$}$, b : $\mbox{${\mathbb Z}$}$) : $\mbox{${\mathbb Z}$}$ == 


1 		 		 if a = b then return a 


2 		 		 if 
a $\equiv$ 0 mod2 and 
b $\equiv$ 0 mod2 then return 
gcd(a/2, b/2) 


3 		 		 if 
a $\equiv$ 0 mod2 and 
b $\equiv$ 1 mod2 then return 
gcd(a/2, b) 


3 		 		 if 
a $\equiv$ 1 mod2 and 
b $\equiv$ 0 mod2 then return 
gcd(a, b/2) 


4 		 		 if a > b then return 
gcd((a - b)/2, b) else  return 
gcd((b - a)/2, a)

1. Let n_a and n_b the number of bits (in binary-expansion) of a and b respectively. Give an upper bound for the number of reursive calls needed to compute gcd(a, b)?
2. Give an upper bound for the number of machine word operations needed for computing gcd(a, b).

Answer 2  

Answer 3