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 \mod{2}$
 and 
$b\equiv 0 \mod{2}$
 then return 
${\gcd}(a/2, b/2)$
 


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


3 		 		 if 
$a \equiv 1 \mod{2}$
 and 
$b\equiv 0 \mod{2}$
 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