
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)/^{2}) log aThis is approximately 1.9405^{.} log_{10} 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 References:
Chris K. Caldwell © 19992018 (all rights reserved)
