Need math function (or algorithm) for reducing fractions

I need to find a C++ math library function for reducing fractions, but have not been able to find one. Is there one available? If not, can you help me with an algortihm to do this i.e. how to get an answer of 3/5 when the input was 6/10?
englmAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

q2guoCommented:
The following function is not the most efficient funciton for doing fraction reduction.  But its the only one I can come
up with in 2 minutes.

The argument d and n represent denominator and neminator respectively.


void Reduce(int &d, int &n) {
    for (int i = n/2; i > 1; i--) {
        if ( (n%i) == 0) {
            if ( (d%i) == 0) {
                 n = n / i;
                 d = d / i;
                 break;
            }
        }
    }
}
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
ozoCommented:
//Heres one Euclid came up with over 2 millennia ago
int gcd(int a,int b){
  while( b ){
    int c;
    c = a%b;
    a = b;
    b = c;
  }
  return a;
}

main(int argc,char *argv[]){
   int d,n,f;
   d = atoi(argv[1]);
   n = atoi(argv[2]);
   f = gcd(d,n);
   printf("%d/%d\n",d/f,n/f);
}

0
ozoCommented:
(If n was supposed to represent the numerator, I think I got my variable names backwards)

But it looks like Reduce(4,4) will only reduce to 2/2
and Reduce(4,-4) seems to have an even worse problem.
0
Rowby Goren Makes an Impact on Screen and Online

Learn about longtime user Rowby Goren and his great contributions to the site. We explore his method for posing questions that are likely to yield a solution, and take a look at how his career transformed from a Hollywood writer to a website entrepreneur.

Ready4DisCommented:
Why (q2guo) do you start at n/2? Shouldn't you check to see which is heigher?  What if the fraction is 10/2.? It will return 10/2 which can be 5/1...
0
q2guoCommented:
Ready4Dis, I assumed that the fraction is a pure one, meaning that the numerator is always smaller that the denominator.
0
ozoCommented:
Then if n is assumed to be smaller than d, shouldn't you have started with d/2?
(I think that's what confused my labels:-) fortunately, the gcd approach doesn't depend such assumptions.
0
q2guoCommented:
ozo: why would you start with d/2?  Since n is smaller than d
all i(s) between d/2 and n/2 are just extra work.
0
ozoCommented:
Given a fraction like 2/10, with the numerator 2 smaller than the denominator 10,
starting i=n/2 i.e. i=1 will fail to reduce it to 1/5
(with a fraction like 10/2, since n=10 and d=2, i=n/2 would start at 5, so Reduce(2,10) would find (10/2)/(2/2) = 5/1)

0
q2guoCommented:
Ok, here is the function again

void Reduce(int &d, int &n) {
        int temp = (d >= n ? d : n);
        for (int i = temp; i > 1; i--) {
            if ( (n%i) == 0) {
                if ( (d%i) == 0) {
                     n = n / i;
                     d = d / i;
                     break;
                }
            }
        }
}
0
ozoCommented:
Still has a problem with -10/2
Here's my (Euclid's) function again with the variables renamed:

int gcd(int a,int b){
  while( b ){
    int c = a%b;
    a = b;
    b = c;
  }
  return a;
}

main(int argc,char *argv[]){
   int n,d,i;
   n = atoi(argv[1]);
   d = atoi(argv[2]);
   i = gcd(n,d);
   printf("%d/%d\n",n/i,d/i);
}


0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.