# Greatest Common Factor Nightmare

Discussion in 'Mac Programming' started by bobber205, Jan 31, 2007.

1. ### bobber205 macrumors 68020

Joined:
Nov 15, 2005
Location:
Oregon
#1
I am able to compute a wonderful greatest common factor if the number on the numerator is larger than the denomiator. If it isn't, right now I am only outputting the fraction as the user entered it.

This obviously doesn't work well. It does for fractions that don't reduce like 2/5 but ones like 4/6 I am confused on how to do.

Help is appreciated.

Code:
```int CalcGCD(int numer, int denom) {
int top = numer;
int bottom = denom;
int m = 0;
int n = 0;
//m = top/bottom;
//n = top%bottom;
int tmp(0),tmp2(0);
m = top;
n = bottom;

m = top/bottom;
n = top%bottom;

while (1) {

if (n == 0) {
return m; //m is the gcd
}
else {
//time to do it again fool!

int tmp = m/n;

int tmp2 = m%n;
n = tmp2;

}

cout << m << "\t" << n << endl;
}
```

2. ### toddburch macrumors 6502a

Joined:
Dec 4, 2006
Location:
Katy, Texas
#2
Ah, the 'ol Euclid Algorithm. Page 2 of the Art of Computer Programming.

Code:
```# Ruby method to find the greatest common divisor

def findGCD(num1, num2)
if num1 % num2==0 then return num2 ;
else return findGCD(num2, num1 % num2 ) ;
end ;
end ;

puts "GCD of 200 & 5 is #{findGCD(200,5)}" ;
puts "GCD of 5 & 200 is #{findGCD(5,200)}" ;

```
I'll let you convert it to C++!

Todd

3. ### toddburch macrumors 6502a

Joined:
Dec 4, 2006
Location:
Katy, Texas
#3
(umm... just finished dinner - Lasanga).

Here's some C code I cobbled together from the Ruby example.

Code:
```#include <stdio.h>

int CalcGCD(int num1, int num2)
{
if ((num1 % num2) == 0) return num2; //num2 is the gcd
else return CalcGCD(num2, num1 % num2) ;
}

int main (int argc, const char * argv[])
{
printf("GCD of 200 and 5 is %i\n" , CalcGCD(200,5));
printf("GCD of 5 and 200 is %i\n" , CalcGCD(5,200));
printf("GCD of 200 and 3 is %i\n" , CalcGCD(200,3));
printf("GCD of 3 and 200 is %i\n" , CalcGCD(3,200));
printf("GCD of 4 and   6 is %i\n" , CalcGCD(4,  6));
printf("GCD of 6 and   4 is %i\n" , CalcGCD(6,  4));
return 0;
}```
Todd

4. ### bobber205 thread starter macrumors 68020

Joined:
Nov 15, 2005
Location:
Oregon
#4
Hmm. Whenever the answer should be 2/3 this logic dies. Why?

Code:
```int CalcGCD(int numer, int denom) {

cout << "numer: " << numer << endl << "denom: " << denom << endl;

int remainder = numer%denom; //the remainder
int divisor = numer/denom; //what's left from the division (integer division)

cout << "remainder: " << remainder << endl << "divisor: " << divisor << endl;

if (remainder == 0) {
cout << "returning now" << endl;
return divisor;
}
else {
cout << "going again." << endl;
int newnumer = divisor;
int newdenom = remainder;
return CalcGCD(newnumer, newdenom);
}

return 0;
}```

5. ### toddburch macrumors 6502a

Joined:
Dec 4, 2006
Location:
Katy, Texas
#5
It dies because you are using "divisor" logic. You don't need it. All you need is the numer, denom and remainder.

Code:
```#include <iostream>

int CalcGCD(int numer, int denom) {

std::cout << "numer: " << numer << "\n" << "denom: " << denom << "\n";

int remainder = numer % denom; //the remainder
//int divisor = numer/denom; //what's left from the division (integer division)

std::cout << "remainder: " << remainder << "\n" ; //   don't need this: << "divisor: " << divisor << "\n";

if (remainder == 0) {
std::cout << "returning now" << "\n";
return denom ;   //not divisor
}
else {
std::cout << "going again." << "\n";
//int newnumer = divisor;
//int newdenom = remainder;
return CalcGCD(denom , remainder);   // not divisor or newnumer
}
}

int main (int argc, char * const argv[]) {
// insert code here...
std::cout << "2/3 GCD =" << CalcGCD(2,3) ;
return 0;
}```
Todd

OK, that's three languages tonight... Anyone want Java? LOL!

p.s. Wasn't sure how to resolve "endl", so I changed it to "\n")

6. ### bobber205 thread starter macrumors 68020

Joined:
Nov 15, 2005
Location:
Oregon
#6
Here's what I was trying to "follow"

Was I reading that wrong maybe?

BTW endl is part of std. "std::endl."

Thanks for the help. Did that run for you? I tried 10 and 3 and got 1. Is that right? Oh wait. Is it isn't it?

BTW. for fractions such as this: 4/18. Here's what I think I should do to them. First find the the fractional part that is left over when it's flipped. In this one's case it's 1/2. Then in the 4/18 times the top by 1/2 and the bottom and those are the most common terms. I've tried several fractions and this has worked.

7. ### toddburch macrumors 6502a

Joined:
Dec 4, 2006
Location:
Katy, Texas
#7
Or, the denominator.

m=4, n=6. m is the dividend, n is the divisor.
4/6 = 0, with remainder 4. (r=4) To get the remainder, you do modulus division (4 % 6), not integer division (4 / 6) which yields 0.
m=n. m now equals 6.
n=r. n now equals 4.
Second time through:
m=6, n=4 (they have reversed)
6/4 = 1, remainder=2.
m=n, or m=4
n=r, or n=2
repeat, since n != 0.

Third time through:
m=4, n=2
4/2 = 2, remainder 0
m=n, or m=2
n=r, or n=0
since n=0, we are done, and m, 2, is the answer.

So, yes, you were reading it wrong.

Thanks for the tip on std::endl. I'm new to C++.

Yes, it ran for every test case I threw at it. (Well, except for the n=0 case...) 10/3 GCD=1, which means, there is not a divisor that goes into both values other than 1, therefore, the fraction cannot be reduced.

Euclid's algorithm works pretty good. With the amount of code you are talking about to parse fractions, flip them around, and do all the manipulation to multiply by 1/2 or some other derived value, I would hate to have to maintain the code and debug it. However you want to do it is up to you.

Todd

8. ### bobber205 thread starter macrumors 68020

Joined:
Nov 15, 2005
Location:
Oregon
#8
I at last got it. I found the GCD regardless of order of the numbers.

I should have known that something silly like if the first number was bigger made a difference should have been a clue that I wasn't doing it right.

Depending on cases, I did the appropriate thing. I even have negative numbers taken into account. All numbers are made postiive and then at the end when the result is printed, I take care of it then.

BTW XOR in C++ is a "^".

If you want the code, send me a pm.