Archived

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

FrigidHelix

Reducing a fraction

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
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
Nonono, not all factors are less than the square root, but once you find the factor less than the square root then the original value divided by that factor gives you the associated "above square root" factor.

So, the square root of 130 is around 11.4. Incrementing you''d get to 10. from there, you first check 130/10 as being a factor of both the numerator and the denomitor since that number would be higher (since the first value is less than the square root), and then you''d check 10 itself in comparison to the numerator and the denominator. If you need more of an explanation I''ll post an algorithm.

--------------------
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
Sounds like the assignment that I am doing right now.
I have to create a fraction calculator using unix redirection and reduce the fraction down to lowest terms if possible.

what I did was declared two variables one int and one a float.
I did a for loop using the number that I wanted to reduce.
I divided it by itself -1.. until the two numbers matched .. and that''s how I got a factor. I am still looking on how to make it compare to find a common factor for both parts of the fraction. (I cannot use arrays). But I''ll solve it later.

Share this post


Link to post
Share on other sites
Here's what I was explaining. It's pretty self explanitory, if something is unclear, just ask.

I also made a bool for sign as it makes calulations faster (quicker implementation) and it allows both the numerator and the denominator to be unsigned.


    
// Fraction.h

#include<iostream.h>

class Fraction
{
public:
Fraction()
: bIsPositive(true), Numerator(0), Denominator(1)
{}
Fraction( const bool IsPositive_Init, const unsigned long int Numerator_Init, const unsigned long int Denominator_Init )
: bIsPositive(IsPositive_Init), Numerator(Numerator_Init)
{ if( Denominator_Init ) Denominator = Denominator_Init; else cout << "ERR: Invalid denominator"; }
Fraction( const long int Numerator_Init, const long int Denominator_Init );
Fraction& Reduce();
Fraction operator*( Fraction Frac ) const;
Fraction operator/( const Fraction& Frac ) const;
unsigned long int GetNumerator() const
{ return Numerator; }
unsigned long int GetDenominator() const
{ return Denominator; }
bool IsPositive() const
{ return bIsPositive; }
Fraction& Invert()
{ unsigned long int Temp = Numerator; Numerator = Denominator; Denominator = Temp; return *this; }
Fraction& Opposite()
{ bIsPositive = !bIsPositive; return *this; }
protected:
static bool IsAFactor( unsigned long int* Value, unsigned long int PossibleFactor )
{ return *Value % PossibleFactor == 0; }
bool bIsPositive;
unsigned long int Numerator, Denominator;
};

inline ostream& operator<<( ostream& os, const Fraction& Frac )
{
if( !Frac.IsPositive() )
os << '-';
return os << Frac.GetNumerator() << '/' << Frac.GetDenominator();
}



  
// Fraction.cpp


#include<math.h>
#include"Fraction.h"

Fraction::Fraction( const long int Numerator_Init, const long int Denominator_Init )
{
if( Numerator_Init < 0 )
{
Numerator = -Numerator_Init;
if( Denominator_Init < 0 )
{
Denominator = -Denominator_Init;
bIsPositive = true;
}
else
{
Denominator = Denominator_Init;
bIsPositive = false;
}
}
else
{
Numerator = Numerator_Init;
if( Denominator_Init < 0 )
{
Denominator = -Denominator_Init;
bIsPositive = false;
}
else
{
Denominator = Denominator_Init;
bIsPositive = true;
}
}
}

Fraction& Fraction::Reduce()
{
if( !Numerator )
{
Denominator = 1;
return *this;
}
if( Numerator == Denominator )
{
Numerator = Denominator = 1;
return *this;
}
unsigned long int *LesserValue, *GreaterValue;
if( Numerator < Denominator )
{
LesserValue = &Numerator;
GreaterValue = &Denominator;
}
else
{
LesserValue = &Denominator;
GreaterValue = &Numerator;
}
unsigned long int SquareRoot = (unsigned long int)(sqrt(*LesserValue));
unsigned int GreatestCommonFactor = 1;
if( IsAFactor( GreaterValue, *LesserValue ) )
{
*GreaterValue /= *LesserValue;
*LesserValue = 1;
return *this;
}
for( unsigned long int LowFactor = 2, HighFactor; LowFactor <= SquareRoot; LowFactor++ )
{
if( !IsAFactor( LesserValue, LowFactor ) )
continue;
if( IsAFactor( GreaterValue, HighFactor = *LesserValue / LowFactor ) )
{
GreatestCommonFactor = HighFactor;
break;
}
else
if( IsAFactor( GreaterValue, LowFactor ) )
GreatestCommonFactor = LowFactor;
}
Numerator /= GreatestCommonFactor;
Denominator /= GreatestCommonFactor;
return *this;
}

Fraction Fraction::operator*( Fraction Frac ) const
{
Fraction TempCopy = *this;
TempCopy.Reduce();
Frac.Reduce();
Fraction Temp1( TempCopy.Numerator, Frac.GetDenominator() ), Temp2( Frac.GetNumerator(), TempCopy.Denominator );
Temp1.Reduce();
Temp2.Reduce();
return Fraction( bIsPositive == Frac.IsPositive(), Temp1.GetNumerator() * Temp2.GetNumerator(), Temp1.GetDenominator() * Temp2.GetDenominator() );
}

Fraction Fraction::operator/( const Fraction& Frac ) const
{
Fraction TempInvert = Frac;
return *this * TempInvert.Invert();
}




        
// main.cpp

#include"Fraction.h"

int main()
{
Fraction Test( 6, -54 );
cout << "Original Fraction: " << Test << endl;
cout << "Reduced Fraction: " << Test.Reduce() << endl;

const Fraction Multiply( -32000, -24000 );
cout << "Secondary Fraction: " << Multiply << endl;
cout << "The product of " << Test << " and " << Multiply << " is " << Test * Multiply << endl;

const Fraction Divide( 368, -492 );
cout << "Tertiary Fraction: " << Divide << endl;
cout << Test << " divided by " << Divide << " is " << Test / Divide << endl;

return 0;
/* Outputs:

Original Fraction: -6/54
Reduced Fraction: -1/9
Secondary Fraction: 32000/24000
The product of -1/9 and 32000/24000 is -4/27
Tertiary Fraction: -368/492
-1/9 divided by -368/492 is 41/276

*/

}


EDIT: I just added multiplication and division support if you want to check it out. I'll probably add addition and subtraction support now since I already went this far.


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

[edited by - Matt Calabrese on March 24, 2002 1:46:52 AM]

Share this post


Link to post
Share on other sites
This is all very well and good, but what''s the point? I mean, there''s plenty of numbers out there which can''t be represented by fractions (in fact, there''s an infinite number of them!)

How''re you going to implement the square root function? What''s the square root of 2?

Of course, this method is good for finite decimal numbers.


codeka.com - Just click it.

Share this post


Link to post
Share on other sites
Dean -- it's use is for educational purposes.

... and have you never used the sqrt function declared in math.h ? That's what you use for getting the square root of a number (in double precision -- also sqrtf for float).

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

[edited by - Matt Calabrese on March 24, 2002 1:51:27 AM]

Share this post


Link to post
Share on other sites
I just added multiplication and division with cross-canceling support to my example code post. I''ll add addition and subtraction now that I''m already this far.

--------------------
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
quote:
Original post by Dean Harding
How''re you going to implement the square root function? What''s the square root of 2?


Obviously the square root of two will be represented as a (reduced) fraction! Oh wait...

-pirate_dau

Share this post


Link to post
Share on other sites
quote:
Original post by Matt Calabrese
... and have you never used the sqrt function declared in math.h ? That''s what you use for getting the square root of a number (in double precision -- also sqrtf for float).



Yes, well... I meant how would you represent the square root of 2 with fractions? You can''t. You can approximate it, but then what''s the point? I mean, you can approximate it with floating point numbers as well.


codeka.com - Just click it.

Share this post


Link to post
Share on other sites
quote:
Original post by pirate_dau
Obviously the square root of two will be represented as a (reduced) fraction! Oh wait...



You can''t represent the square root of 2 as a fraction. It can be approximated, but since the square root of 2 has an infinite number of (non-repeating) digits after the decimal point, it''s impossible to represent in fraction form. Tell me the fraction form of pi? You can approximate it (22/7 is a good one) but it''s only accurate to a certain number of decimal places.

Clearly, no computer can represent the square root of 2 exactly (since it''s got infinite digits and we only have finite memory) but still, I think there''s better ways to do this (like using arbitrary precision algorithms, for example).

Anyway, it''s still a great subject for learning, so I''ll let you guys get back to it...


codeka.com - Just click it.

Share this post


Link to post
Share on other sites
A computer can store root 2 in exact form, it is just the way you interpret data. Just like we can write the square root sign and a 2 on a piece of paper, a computer can store that. Then, when you do operations, if you get to something where you are multiplying root 2 by root 2, you can change it to a straight out integer.

Trying is the first step towards failure.

Share this post


Link to post
Share on other sites