Archived

This topic is now archived and is closed to further replies.

Reducing a fraction

This topic is 6017 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I am writing an arithmatic program, and I figured it would be to my advantage to represent decimal numbers as fractions. This way, I can easily add/multiply with other numbers of type fraction. The only problem is, when it comes time to reduce the numbers, my program takes forever. For example consider the following operation: 30.8155 + 15.1508 = 45.9663 My program would represent both 30.8155 and 15.1508 as fractions, and would compute the resulting fraction 229831500/5000000. This step goes by very quickly. But when it comes time to investigate this for reduction, the application hangs for some 5 minutes before outputting the result. Here is the source for the reduction function. Note, it worked fine when I was dealing with smaller fractions, like 4 + 1/8.
  // Simplify matters, by ensuring that only the numerator can have a negative value

if( Denominator < 0 )
{ Numerator *= -1; Denominator *= -1; }

int factor= (abs(Numerator)>Denominator) ? abs(Numerator) : Denominator;
for( ; factor>1; factor-- )
{
if((Numerator%factor)==0 && (Denominator%factor)==0 )
{
Numerator /= factor;
Denominator /= factor;
}
}  
What I'm asking is, what is a more efficient way of writing a fraction reducing algorithm. Edited by - FrigidHelix on March 23, 2002 6:26:48 PM

Share on other sites
The problem is that factor is going from the highest possible number to 1. Try going from 1 to the highest number. I made a program like that and it reduced your fraction instantly.

Share on other sites
Also, when you reduce it, set factor back to 2 to restart the loop.

Share on other sites
One problem is you are testing all of the values between 1 and the number.

Think about this mathematically -- you only have to go up to the square root of the number! Once you pass that point, multiplication is sort of a "mirror image." I''m probably explaining this poorly, but if you think about it, you''ll probably understand. Sorry I can''t take more time to explain, gotta go to a shoot! Good luck!

--------------------
Matthew Calabrese
Realtime 3D Orchestra:
Programmer, Composer,
and 3D Artist/Animator
"I can see the music..."

Share on other sites

    int factor = 2;if(numerator == denominator) { numerator = denominator = 1; }while( (factor < denominator) && (factor < numerator) ) {    if( (denominator % factor) == 0 && (numerator % factor) == 0) {      numerator /= factor;      denominator /= factor;      factor = 1;   }   factor++;}

-pirate_dau

[edited by - pirate_dau on March 23, 2002 6:54:24 PM]

Share on other sites
quote:
Original post by Matt Calabrese
One problem is you are testing all of the values between 1 and the number.

Think about this mathematically -- you only have to go up to the square root of the number! Once you pass that point, multiplication is sort of a "mirror image." I''m probably explaining this poorly, but if you think about it, you''ll probably understand. Sorry I can''t take more time to explain, gotta go to a shoot! Good luck!

yeah, that makes sense. but if you reset the factor back to one each time, you''ll never get past the half way point

Share on other sites
Nice algorithm pirate_dau. Goes hundreds of times faster than my version.

Share on other sites

  int gcd(int n, int m){   n = abs(n);   m = abs(m);   for(;;)   {      if (m == 0) return n;      n %= m;      if (n == 0) return m;      m %= n;   }}void Rational::Reduce(){   int factor = gcd(Numerator, Denominator);   Numerator /= factor;   Denominator /= factor;   if (Denominator < 0)   {      Numerator = -Numerator;      Denominator = -Denominator;   }}

[edited by - alexk7 on March 23, 2002 8:53:06 PM]

Share on other sites
Back --

A better explanation of what I said above:

For every factor of a number less than the square root, the number divided by that number is greater than the square root. Obviously the same is the opposite as well. If you were to multiply two numbers together that were both greater than the square root, you''d always get a number greater than the value you want, and if they were both less than the square root, the product would always be too low. So, when you check for factors on one side, you are really implicitly checking for factors on the other side.

Since this is the case, decrementing instead of incrementing is not too smart. This is because since you can implicitly check all the factors by only going up to the square root, you''d want to check the "side" of the square root with less numbers. Since you''re squaring, the number is obviously going to be very low in comparisonto the full range of values -- take for example 25: it''s square root is 5. It''s much faster to check 2 through 5 than it is to check 5 through 24. So in short, the fastest way is to loop; checking for factors and incrementing until you reach the square root. You''ll save a lot of time that way.

Also, not that in your first example you gave the number 229831500/5000000. Those values are quite large. While dealing with fractions can be useful and educational, you''d need to set aside quite a lot of space to be sure you''d be able to fit those values in. That''s just something to watch out for.

--------------------
Matthew Calabrese
Realtime 3D Orchestra:
Programmer, Composer,
and 3D Artist/Animator
"I can see the music..."

Share on other sites
Matt, I''m not sure I understand the square root technique. This is how I applied it (unsuccessfully):

Take 130 for example. Its square root is ~ 11.402. If all the factors are less than the square root, than what happens to 13? If I''m not mistaken, 13*10 = 130

1. 1
2. 2
3. 3
Rutin
18
4. 4
JoeJ
14
5. 5

• 14
• 9
• 23
• 9
• 32
• Forum Statistics

• Total Topics
632623
• Total Posts
3007503
• Who's Online (See full list)

There are no registered users currently online

×

Important Information

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!