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).
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. 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