** Next:** 2.2 Binary GCD algorithm
** Up:** 2 Greatest common divisor
** Previous:** 2 Greatest common divisor

The original algorithm of Euclid goes as follows. If *b* = 0 then *d* = *a*
and we stop. Else we compute,
*a* = *b*^{ . }*w* + *r*. We then iterate with
*b* taking the place of *a* and *r* taking the place of *b*.
Since we are dealing with *a*, *b* each involving many (say *N*)
``digits'', each division takes *N*^{2} steps as we saw earlier. Since,
these divisions are iterated until we reach the GCD (which could be 1)
we could iterate *N* times and get a total of *N*^{3} steps. This seems
too large for such a fundamental operation. So we should first get a
better estimate for the number of steps and then take into account the
decreasing sizes of *a* and *b*.

**Lemma 3**
Let *a* > *b* > 0 be such that Euclid's algorithm takes exactly *n* steps
and *a* is the least possible with this property. Then *a* = *F*_{n + 2}
and *b* = *F*_{n + 1}, where *F*_{n} defined inductively by *F*_{0} = *F*_{1} = 1 and
*F*_{n + 1} = *F*_{n} + *F*_{n - 1}.

The proof is related with *continued fractions* from which it also
follows that *F*_{n} is like *C*^{n} for some constant *C* > 1. Thus it
follows that we actually need only a constant multiple of log(*N*)
steps. It can also be noted that *a* and *b* are often of the same
size (especially after the first iteration). In this case *w* is small
so the long division takes less steps than expected.
We will study the proof of the lemma when we look at real quadratic
number fields.

** Next:** 2.2 Binary GCD algorithm
** Up:** 2 Greatest common divisor
** Previous:** 2 Greatest common divisor
Kapil Hari Paranjape
2002-10-20