# Help, Algorithm to optimize fraction number

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

1. ### nietsni3Guest

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_CoolModerator

Joined:
Jun 30, 2003
Messages:
301,205
1,195
Use the euclidean algorithm to find the GCF, divide top and bottom by that, and you're done.

3. ### Joe_CoolModerator

Joined:
Jun 30, 2003
Messages:
301,205
1,195
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. ### nietsni3Guest

oh thanks alot

Joined:
Jun 30, 2003
Messages:
301,205