Migration complete - please let us know if anything isn't working.
Lamé's theorem
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)/π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
References:
- Knuth81
- 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]]
Printed from the PrimePages <t5k.org> © Reginald McLean.