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 = u_n+2 and b = u_n+1 (where u_n 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 a ≤ b is

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

This is approximately 1.9405^. log₁₀ 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

• at most five times the number of digits in the larger of a or b, and
• on the average is less than twice that number of digits.

See Also: EuclideanAlgorithm

References:

Knuth81

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