The Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.


Math Forum » Discussions » Inactive » Historia-Matematica

Topic: [HM] counting operations
Replies: 6   Last Post: May 20, 2000 11:38 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Carlos Cesar de Araujo

Posts: 3
Registered: 12/3/04
Re: [HM] counting operations
Posted: May 8, 2000 11:05 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


A theorem due to the French mathematician and engineer Gabriel Lam\'e
(1795-1870) 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. A-B 19 (1844), pp. 867-869.

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






Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.