MacRumors Forums Greatest Common Factor Nightmare

 Jan 31, 2007, 04:34 PM #1 bobber205 macrumors 68020     Join Date: Nov 2005 Location: Oregon Greatest Common Factor Nightmare 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; }``` __________________ Gyaboo!!!! Last edited by bobber205; Jan 31, 2007 at 04:41 PM. 0
 Jan 31, 2007, 05:40 PM #2 toddburch macrumors 6502a   Join Date: Dec 2006 Location: Katy, Texas 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 0
 Jan 31, 2007, 06:31 PM #3 toddburch macrumors 6502a   Join Date: Dec 2006 Location: Katy, Texas (umm... just finished dinner - Lasanga). Here's some C code I cobbled together from the Ruby example. Code: ```#include 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 Last edited by toddburch; Jan 31, 2007 at 06:41 PM. 0
 Jan 31, 2007, 07:46 PM #4 bobber205 Thread Starter macrumors 68020     Join Date: Nov 2005 Location: Oregon 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; }``` __________________ Gyaboo!!!! 0
 Jan 31, 2007, 08:09 PM #5 toddburch macrumors 6502a   Join Date: Dec 2006 Location: Katy, Texas It dies because you are using "divisor" logic. You don't need it. All you need is the numer, denom and remainder. Code: ```#include 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") 0
Jan 31, 2007, 09:25 PM   #6
bobber205
macrumors 68020

Join Date: Nov 2005
Location: Oregon
Here's what I was trying to "follow"

Quote:
 The most common algorithm for computing the GCD is known as Euclid’s algorithm. The algorithm is as follows: Let m and n be the two integer values. Divide m by n. Save the divisor in m and save the remainder in n. If n is 0, then stop: m contains the GCD. Otherwise repeat the process.
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.
__________________
Gyaboo!!!!

Last edited by bobber205; Jan 31, 2007 at 09:30 PM.
0
Jan 31, 2007, 10:58 PM   #7
toddburch
macrumors 6502a

Join Date: Dec 2006
Location: Katy, Texas
Quote:
 Originally Posted by Dictionary.com Divisor: 1. a number by which another number, the dividend, is divided.
Or, the denominator.

Quote:
 Let m and n be the two integer values.
m=4, n=6. m is the dividend, n is the divisor.
Quote:
 Divide m by n.
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.
Quote:
 Save the divisor in m
m=n. m now equals 6.
Quote:
 and save the remainder in n.
n=r. n now equals 4.
Quote:
 If n is 0, then stop: m contains the GCD. Otherwise repeat the process.
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
0
 Feb 1, 2007, 12:08 AM #8 bobber205 Thread Starter macrumors 68020     Join Date: Nov 2005 Location: Oregon 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. __________________ Gyaboo!!!! 0

 MacRumors Forums