C++ Algorithm

[Edwin_Drood_1870]

How do you find the least common denominator for a fraction?
I am using a class to create a custom data class for fractions. It will be implemented with a class "Fraction." The data will be two integers, numerator and denominator.
The problem is, I have to be able to reduce each fraction. For instance, 8/2 should equal 4/1 and 2/8 should equal 1/4. I was told that if you took either number, divided it by the other ( like 127/9 ) and kept divideding then the divisor by the remainder, you would come up with the LCM. Is this true? how do you implement this?

[Zaei]

while((num%2 == 0)) && (dem%2 == 0))
{
   num = num / 2; dem = dem / 2;
}

Should work, I just came up with it in my head... Just says that if both the numerator and denominator are even, divide both by 2.

Z.

[Edwin_Drood_1870]

What if they are odd?

[HarryW]

I don't know if the remainders method you mentioned would work, but I guess it might *Shrug*

Intuitively, it seems that the logical way to do this is to find the highest common factor (HCF) of the two numbers and divide them both by this, and keep finding the HCF and dividing until the HCF is 1.

Finding the HCF of two integers can be done algorithmically by repeatedly subtracting the lesser from the greater until they are equal. When they are equal to each other, they are also equal to the HCF of the original two integers. For example, to find the HCF of 30 and 9:

30 ... 9 (start)
21 ... 9 (subtract 9 from 30)
12 ... 9 (subtract 9 from 21)
3 ..... 9 (subtract 9 from 12)
3 ..... 6 (subtract 3 from 9)
3 ..... 3 (subtract 3 from 6)
They are equal so HCF is 3

I hope that helps.

[Zaei]

Ok, lets rewrite...

int max = Max(num, dem);  //function Max(...) returns highest value...
for(int i = max; i > 0; i--)
{
  while((num%i == 0)) && (dem%i == 0))
  {
     num = num / i; dem = dem / i;
  }
}

This one seems more likely to work... Tell me what you find...

Z.

[edit]
And please try to remember that its almost 1 AM... =)

[Edwin_Drood_1870]

I got it. All you do keep dividing by the divisor and using the remainder as the next divisor (well, sort of)

void Rational::ReduceFraction()
{
int remainder;
int dividend;
int divisor;

dividend = abs(numr);
divisor = abs(denom);

while(true)
{
remainder = dividend % divisor;

if (remainder == 0)
break;
else
{
dividend = divisor;
divisor = remainder;
}
}

numr /= divisor;
denom /= divisor;

}