How bad could it be?

Let's try to learn something about the worst-case running-time of the Euclidean GCD algorithm. If you actually run through the example on some inputs, you'll see that the remainders keep getting smaller and smaller until we hit zero and, in practice, they seem to gert small fast. So a bad case for the Euclidean algorithm is when they get small slowly, and it takes lots of steps to get to zero. So, the key is this: what gives us big remainders? Well, in dividing $a$ by $b$, if $b$ is too close to $a$, the quotient is 1 and there is only a small amount of leftover, which is the remainder, $r$. On the other hand, if $b$ is small, then $r$ is necessarily small, since it must be less than $b$. So, as with Bears, the middle is "just right". If $b = \lfloor a/2 \rfloor + 1$ we get the largest possible remainder. Even so, we have the following: \[ r \lt 1/2 a \] If we apply this to the Euclidean algorithm, we get the following (where $r_i$ is the remainder at the $i$th step: \[ \begin{array}{cccl} a&b&r&\text{bound}\\ \hline a&b&r_1&\lt a/2\\ b&r_1&r_2&\lt b/2\\ r_1&r_2&r_3&\lt a/2^2\\ r_2&r_3&r_4&\lt b/2^2\\ \vdots&\vdots&\vdots&\vdots\\ r_{2k-2}&r_{2k-1}&r_{2k}&\lt b/2^k\\ \end{array} \] So, after $2 \lg b$ steps we have $r_{2\lg b} \lt 1$ which means the algorithm is done. This gives an upper bound of $2 \lg b$ on the number of steps (i.e. recursive calls). Note, however, that this is not the same as the running time. Why? Because each step requires a "mod" operation, and when the integers involved are too big to fit in a machine word, these mods will no longer take constant time!

A lower bound on how bad it could be

The Unit Notes have a nice derivation of a $\Omega(\lg b)$ lower bound on the number of steps in the Euclidean algorithm. It comes from the observation that consecutive Fibanocci numbers are worst-case input for the Eucliean algorithm.

The Extended Euclidean Algorithm

Read the Unit Notes, but here's the Extended Euclidean Algorithm. It returns not only the GCD, but also the cofactors!

XGCD (Extended Euclidean Algorithm)
Input : Integers a and b
Output: Integers g, s, and t such that g = GCD(a,b) and a s + b t = g

xgcd(a, b)
------------------------
if b == 0
  return (a, 1, 0)
else
  (q, r) = divmod(a, b) ← i.e. q and r are the quotient and remainder
  (g0, s0, t0) = xgcd(b, r)
  return (g0, t0, s0 - t0*q)
          --- --- ---------
           g   s      t