Is the Euclidean Algorithm actually the fastest for reducing fractions?

Discussion in 'Mac Programming' started by MorphingDragon, Oct 19, 2010.

  1. macrumors 603

    MorphingDragon

    Joined:
    Mar 27, 2009
    Location:
    The World Inbetween
    #1
    Is the Euclidean Algorithm actually the fastest for reducing fractions and related integer relations? I've seen some SE books use some strange functions but I was under the impression the the EA was the fastest.

    ---

    And no, I didn't enter that contest I made a post about a 2 weeks ago. I decided my time would be spent better studying for my exams.
     
  2. macrumors G5

    gnasher729

    Joined:
    Nov 25, 2005
    #2
    As long as you make the right decision whether to divide or subtract. (For example 314 / 271: Subtract. 1000000000000 / 3: Divide).
     
  3. macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #3
    The great thing about the Euclidean algorithm is that it is very easy conceptually and can be implemented super fast in practically any language.

    That and it is great because of its wide uses. I've used Euclidean algorithm in table form to:
    *find Greatest common divisor / test relative primeness
    *solve for base case of diophantine equations
    *invert numbers in modular systems..

    probably more I'm not thinking of. (all in TI-BASIC btw)

    Is it the fastest method of finding GCD? Maybe not, I'm sure there have been some extraordinarily clever methods developed in the hundreds of years since Euclid, but it is usually "fast enough".
     
  4. macrumors 603

    Joined:
    Aug 9, 2009
  5. macrumors 68030

    jared_kipe

    Joined:
    Dec 8, 2003
    Location:
    Seattle
    #5

Share This Page