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/