Continued Fractions and the GCD

Robert M. Corless

Thu Feb 29 16:42:01 PST 1996

Some time after I wrote ``Continued Fractions and Chaos'' I remembered that there was an extensive analysis of the connexion between continued fractions and Euclid's algorithm for computing GCD's in Knuth's The Art of Computer Programming, vol 2 (Seminumerical Programming). Section 4.5.3 in particular details the connexion and uses it to analyse the complexity of the Euclidean algorithm.

Knuth's description of the connexion is far superior to mine, and I urge the reader to consult Knuth's book.

Here is a brief Maple version of the algorithm, which assumes with no loss of generality that its input is two positive integers a and b with a > b. 

k := 1;
r[0] := a;
r[1] := b;
while r[k] > 0 do
  n[k] := floor( r[k-1]/r[k] );
  r[k+1] := rem(r[k-1], r[k]);
  k := k + 1;
od;

Using the relation

Additionally, it turns out that my original statements in ``Continued Fractions and Chaos'' had it backward: it is the properties of continued fractions that are used to prove that, in the worst case, the Euclidean algorithm terminates after at most ceil steps, where is the golden ratio, where . In ``Continued Fractions and Chaos'', I claimed that the running time of the Euclidean algorithm gave us this result for continued fractions (perhaps one could prove it this way, as I thought that I had). This is a result that Knuth attributes to Lamé from 1845, so my rather blasé `it is easy to see' sounds rather weak.

However, I think at least the basic idea really is `easy to see'. The basic idea I had in mind when writing ``Continued Fractions and Chaos'', which is the same as that used by Knuth (I haven't seen Lamé's paper so I don't know if Knuth made improvements) is that the slowest the algorithm can go is if the quotients that occur are 1 every time: with q = 1. This gives us Fibonacci numbers and the bound above. According to Knuth, and I believe him, Lamé's result is the first `applied' use of Fibonacci numbers in the literature.

The average case complexity of Euclid's algorithm, on the other hand, is formidably difficult (I had not known that), and was not fully resolved until Knuth himself put the final nail in, in 1976. Further, there are intriguing connections with Gauss' work and ergodic theory--- which I mention later on in ``Continued Fractions and Chaos''---on p. 355 of Knuth's book we see the Gauss measure being used. More on this later, though. Now back to the main paper.

• About this document ...