Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: [HM] counting operations
Posted:
May 8, 2000 11:05 PM


A theorem due to the French mathematician and engineer Gabriel Lam\'e (17951870) establishes an upper bound for the number of divisions required in the Euclidean GCD algorithm. Namely, the number of divisions required to find GCD[a,b] is less than or equal to five (5) times the number of digits of Min[a,b]. Lam\'e's theorem appeared in
Note sur la limite du nombre des divisions, C. R. Acad. Sci. Paris Ser. AB 19 (1844), pp. 867869.
It is viewed by many as the first published analysis of the ``running time'' of a number theoretic algorithm (implying that Euclid's algorithm runs in polynomial time).
Carlos C\e'sar de Ara\'ujo



