The Prime Glossary: Lamé's theorem

Lamé's theorem
(another Prime Pages' Glossary entries)

Glossary:

Prime Pages:

Top 5000:

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 volume 2, Addison-Wesley, Reading MA, 1981. MR 83i:68003 (Annotation available)