// 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;
}
} Reducing a fraction
Author
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.
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
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.
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..."
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..."
How about this:
-pirate_dau
[edited by - pirate_dau on March 23, 2002 6:54:24 PM]
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]
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
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]
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..."
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..."
Author
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
