Jump to content
  • Advertisement

Archived

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

FrigidHelix

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
Share on other sites
How about this:


    
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

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!