Quick C++ reducing a fraction question

[TGCid]

If a user input 4/8, how would you reduce it? I am thinking checking if the top and bottom to see if they can be divide by the same number but it will be too redundant. Is there a build in function that do all the work? Some algorithm/ideas are fine, I don't need the code itself.

 

[br0wn]

what you want is to find the Greatest Common Divisor (GCD),
then you can divide both numbers with the GCD.

Check GCD algorithm (or Euclid alg if you are confident with your
algorithm skill).

 

[hans007]

do a for loop from the top number (4) to 2, on both, if they both mod to 0 then you have a clean divide. Thats the easiest way , then divide both if its a good divide

 

[HigherGround]

#define MIN(a,b) (a < b ? a : b)

// num = numerator
// den = denominator
// div = current divisor
void reduce(int num, int den, int div)
{
int min = MIN(num, den);
if(div > min)
return; // done
if(!(num%div) &amp;&amp; !(den%div)) // can we divide both numerator and denominator?
{
printf(&quot;%d/%d\n&quot;, num/div, den/div);
reduce(num/div, den/div, div);
}
else
reduce(num, den, ++div); // up the divisor by 1 and try again
}

int main(int argc, char* argv[])
{
reduce(4, 8, 2); // start with a nice low divisor (can't be 1!!)
return 0;
}


i have no idea if this is 100% booletproof, but it sure looked like it at 6am if you can find any logic errors drop a line in here. theres absolutly no optimalization being done (like checking for primes, etc), but as far as I know it wroks pretty well. If you have any questions on implementation drop a line over here.

 

[br0wn]

Here is the Euclid's algorithm (faster and more efficient, as
you don't enumerate all numbers for finding the GCD) :

/***************** START FUNCTION *****/
int Euclid(int m, int n)
{
int t;

while (m > 0)
{
t = m;
m = n % m; /* n mod m */
n = t;
}

return n;
}
/************** END OF FUNCTION ******/

Thus given m (numerator) and n (denominator) it will
return the GCD.
Dividing m and n by this number (GCD) will reduced the
fraction.

for example :
Euclid(5, 15) will return 5. /* then divide both 5 and 15 with 5, you will get 1/3 */
Euclid (16, 20) will return 4. /* dividing both 16 and 20 with 4, you will get 4/5 */
Euclid (4, 8) will return 4.
Euclid (3, 7) will return 1.

 

[TGCid]

Ok I think I got it. Thanks you so much again.