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

Euclid's Lemma

Expand Messages
  • michael971
    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?
    • 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 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/
      • djbroadhurst
        ... 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.