## Reading

These notes and
closely review

Unit 3
Section 4.

## 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