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

## 2.1 Euclid's algorithm

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 N2 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 N3 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 = Fn + 2 and b = Fn + 1, where Fn defined inductively by F0 = F1 = 1 and Fn + 1 = Fn + Fn - 1.

The proof is related with continued fractions from which it also follows that Fn is like Cn 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