** We consider the following classical algorithm, which computes the gcd of two integer numbers.
**`
==
`

1 **if**
**then** **return**

2 **if**
**and**
**then** **return**

3 **if**
**and**
**then** **return**

3 **if**
**and**
**then** **return**

4 **if**
**then** **return**
**else** **return**

**
Let
and
the number of bits (in binary-expansion) of
and
respectively.
**

*Marc Moreno Maza *

2008-03-18