Statement

We consider the following classical 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 
$2 \ {\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)$

Let $n_a$ and $n_b$ the number of bits (in binary-expansion) of $a$ and $b$ respectively.