Sorry, an error occurred while loading the content.

## Euclid's Lemma

Expand Messages
• It allows you to find the gcd of two numbers. Is there a formula that predicts the maximum number of steps to get the gcd?
Message 1 of 3 , Jan 21, 2013
• 0 Attachment
It allows you to find the gcd of two numbers.
Is there a formula that predicts the maximum number of steps to get the gcd?
• ... There s a long discussion of the efficiency of the gcd algorithm in Knuth, but I m not sure if it was in Concrete Mathematics or in The Art of Computer
Message 2 of 3 , Jan 21, 2013
• 0 Attachment
On 01/21/2013 07:24 PM, michael971 wrote:
> It allows you to find the gcd of two numbers.
> Is there a formula that predicts the maximum number of steps to get the gcd?

There's a long discussion of the efficiency of the gcd algorithm in
Knuth, but I'm not sure if it was in Concrete Mathematics or in The Art
of Computer Programming. (I don't have either at hand at the moment, so
I can't be more specific.) It was clear that analysis of the efficiency
of GCD was not trivial. You will almost certainly not find a formula,
but you might find some asymptotic bounds.

--
Alan Eliasen
eliasen@...
http://futureboy.us/
• ... http://www.cut-the-knot.org/blue/LamesTheorem.shtml David
Message 3 of 3 , Jan 22, 2013
• 0 Attachment
--- In primenumbers@yahoogroups.com, "michael971" wrote:

> It allows you to find the gcd of two numbers.
> Is there a formula that predicts the maximum number of steps to get the gcd?

http://www.cut-the-knot.org/blue/LamesTheorem.shtml

David
Your message has been successfully submitted and would be delivered to recipients shortly.