Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Euclid's Lemma

Expand Messages
  • Alan Eliasen
    ... 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 1 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/
    • djbroadhurst
      ... http://www.cut-the-knot.org/blue/LamesTheorem.shtml David
      Message 2 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.