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