Help, Algorithm to optimize fraction number

Discussion in 'OT Technology' started by nietsni3, Jan 20, 2005.

  1. nietsni3

    nietsni3 Guest

    i need an algorithm to simplify any given fraction to its smallest terms.
    the one i was thinking about is to decompose both numerator and denominator into prime factors and then cancel out the similar factors. but i think that algorithm is a little awkward because the calculation of finding the primes to factor is a bit hefty. is there any other way more delicate than that?
    thanks
     
  2. Joe_Cool

    Joe_Cool Never trust a woman or a government. Moderator

    Joined:
    Jun 30, 2003
    Messages:
    299,486
    Likes Received:
    614
    Use the euclidean algorithm to find the GCF, divide top and bottom by that, and you're done.
     
  3. Joe_Cool

    Joe_Cool Never trust a woman or a government. Moderator

    Joined:
    Jun 30, 2003
    Messages:
    299,486
    Likes Received:
    614
    Here's the euclidean algorithm as a recursive function in bc:

    define gcf(a,b)
    {
    if(a%b==0)
    {return b}
    {return gcd(b,a%b)}
    }

    1. You take the two numbers A and B (A>B).
    2. Find the integer remainder when A/B and call it C.
    3. If C == 0, then B is your GCF.
    4. If C > 0, assign B's value to A, assign C's value to B, and repeat from step 2.

    It usually doesn't take more than a few steps.
     
    Last edited: Jan 23, 2005
  4. nietsni3

    nietsni3 Guest

    oh thanks alot :)
     
  5. Joe_Cool

    Joe_Cool Never trust a woman or a government. Moderator

    Joined:
    Jun 30, 2003
    Messages:
    299,486
    Likes Received:
    614
    I had a typo, and fixed it in bold. The test is whether C is ZERO, not one.
     

Share This Page