Lamé's theorem

In 1845 G. Lame' proved the following theorem about the number of steps required by the Euclidean algorithm to find the gcd(a,b):

For a given positive integer n, let a > b be the least integers such that Euclid's algorithm applied to a and b requires exactly n division steps. Then a = un+2 and b = un+1 (where un is the nth Fibonacci number).

From this we see that the Euclidean algorithm for numbers at most N will take at most ceiling(4.8 log(N)/log(10) - 0.32) steps.

Heilborn and Porter proved that the average number of steps the number of steps in the Euclidean algorithm for numbers ab is

((12 log 2)/π2) log a

This is approximately 1.9405. log10 a) steps (see [Knuth81 section 4.5.3]).

A simpler way to say these results is that the number of steps in Euclid's algorithm for gcd(a,b) is

See Also: EuclideanAlgorithm


D. E. Knuth, Seminumerical algorithms, 2nd edition, The Art of Computer Programming Vol, 2, Addison-Wesley, 1981.  Reading MA, MR 83i:68003 [This book is an excellent reference for anyone interested in the basic aspects of programming the algorithms mentioned in these pages. New edition: [Knuth97]]
Printed from the PrimePages <> © Reginald McLean.