Lamé's theorem
(another Prime Pages' Glossary entries)
The Prime Glossary
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 = 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 a < b is

((12 log 2)/pi2) 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

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



Chris K. Caldwell © 1999-2017 (all rights reserved)