[U-Volt]

HI everyone. Figured I'd go ahead and introduce myself....

My name is Matt and I'm currently in my 4th Semester as a Computer Science major. In my C++ class, we just did a Fraction reduction program. It will reduce a Fraction to its lowest terms. We went over it in class, but I just wanted to see if anyone can clarify how exactly the following for loop reduces the Fraction. Just kind of step me through it if you can and explain how it does what it does. Thanks in advance for the help!

void Fraction::reduceFraction()
{
   int a = 0;         
   int b = 0;         
   int i = 0;           
   a = denominator;         
   b = numerator;           
 
   for (i = 50; i > 1; i--)         
   {                 
        if ((a % i == 0) && (b % i == 0))                 
           {                         
              a /= i;                         
              b /= i;                 
           }         
   }           
 
  denominator = a;         
  numerator = b; 

  cout << "Reduced Fraction: " << numerator << "/" << denominator << endl;
}

[PlasticineGuy]

It loops each number from 2 to 50 for (i = 50; i > 1; i--) to see if it divides evenly with both the numerator and denominator if ((a % i == 0) && (b % i == 0)), and if so divides it.

The % (modulus) operator returns the remainder of a divided by i.

[Martyr2]

Very simple, it starts at 50 and counts its way down. Each time it checks does the value of the loop divide evenly into the denominator and the numerator.

For instance if we have 25/50 it will loop at 50 and not until it hits i = 25 will it go into the if statement since both "a" and "b" are both dividable by 25. Remember that the modulus operator here is returning the "remainder" of the division. So 25 % 25 will equal 0 and 50 % 25 will also equal zero.

Now once in the if statement we use integer division to determine the new values of "a" and "b". So 25 /= 25 is going to assign "1" back to "a" and 50 / 25 is going to assign 2 back to "b". Now that "a" and "b" has been reduced, we continue with the loop until we hit 1.

Assume we had 100 / 200. When we start at 50 we are going to go into the if statement since 50 fits into both 100 and 200. "a" would end up being 2 and "b" would be 4. We then continue the loop until we finally reach i = 2 in which case 2 / 2 = 1 would be assigned back to "a" and 4 / 2 would equal 2 which would be assigned to "b". That would be a case where the loop would have to do two reductions.

Hopefully that clarifies. The if statement checks for if the factors will divide evenly into top and bottom and the integer division will set the numerator/denominator to the values of how many times the index will evenly go into them.

[NickDMax]

One should note that this is not a terribly great way to reduce fractions. For example if you were to ask it to reduce 106/159 it would not reduce this fraction to 2/3.

The reason is that 106 = 53 * 2 and 159 = 53 * 3 so neither number has a common divisor less than 50. In fact the greatest common divisor is 53. If you gave it the fraction 212/318 it would say the reduced form was 106/159 rather than the correct answer of 2/3.

(53 * 2 * 2) / (53 * 2 * 3) --> GCD = 53 * 2

You could make one small change to fix the algorithm as-is:
for (i = denominator; i > 1; i--) or
for (i = numerator; i > 1; i--)

This would work but of you have a fraction like 2/1024 the first version would have to iterate from 1024 down to 2 before it found a common denominator. likewise to reduce 1024/2 the second for-loop would have to do a lot of work to reduce this. So perhaps a better way would be:

for (i = min(numerator, denominator); i > 1; i--)

again this would work... but there are better algorithms for finding common divisor.

[U-Volt]

Hey, thanks a lot for the help guys. Everything is much clearer now. I was actually going to ask my instructor for clarification in class tomorrow, but I didn't want to wait any longer. It was really eating at me.

@NickDMax: Thanks for the insight! I was actually just thinking last night about the possibility of the GCF being bigger than 50. I'm going to take your advice and mess around with the code a bit to see if I can find a more efficient way to do this.

Thanks again everyone. This site is awesome for someone like me that is really enjoying learning his chosen trade. I'll definitely be around in the future, so I'll catch ya later!