Jan 31, 2007, 04:34 PM  #1 
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 
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)}" ; Todd 

0 
Jan 31, 2007, 06:31 PM  #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; } Last edited by toddburch; Jan 31, 2007 at 06:41 PM. 

0 
Jan 31, 2007, 07:46 PM  #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; }
__________________
Gyaboo!!!! 

0 
Jan 31, 2007, 08:09 PM  #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; } 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  
Here's what I was trying to "follow"
Quote:
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  
Quote:
Quote:
Quote:
Quote:
Quote:
Quote:
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. Glad I could help. Todd 

0 
Feb 1, 2007, 12:08 AM  #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.
__________________
Gyaboo!!!! 

0 
«
Previous Thread

Next Thread
»
Thread Tools  Search this Thread 
Display Modes  


Similar Threads  
thread  Thread Starter  Forum  Replies  Last Post 
The Most Common GPU's. Probably Not What You Were Guessing + Most Common Gaming Macs  rmbrown09  MacBook Pro  10  Aug 6, 2010 01:07 PM 
Do you prefer the old form factor or new form factor?  DoNoHarm  iPhone  11  Jul 20, 2010 12:14 PM 
Cool factor or Pretentious factor?  Simgar988  iPad  27  Apr 8, 2010 11:29 AM 
All times are GMT 5. The time now is 02:17 AM.