Register FAQ / Rules Forum Spy Search Today's Posts Mark Forums Read
Go Back   MacRumors Forums > Apple Systems and Services > Programming > Mac Programming

Reply
 
Thread Tools Search this Thread Display Modes
Old Jan 31, 2007, 04:34 PM   #1
bobber205
macrumors 68020
 
bobber205's Avatar
 
Join Date: Nov 2005
Location: Oregon
Send a message via AIM to bobber205 Send a message via Yahoo to bobber205 Send a message via Skype™ to bobber205
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.
bobber205 is offline   0 Reply With Quote
Old Jan 31, 2007, 05:40 PM   #2
toddburch
macrumors 6502a
 
Join Date: Dec 2006
Location: Katy, Texas
Send a message via AIM to toddburch Send a message via MSN to toddburch
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
toddburch is offline   0 Reply With Quote
Old Jan 31, 2007, 06:31 PM   #3
toddburch
macrumors 6502a
 
Join Date: Dec 2006
Location: Katy, Texas
Send a message via AIM to toddburch Send a message via MSN to toddburch
(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

Last edited by toddburch; Jan 31, 2007 at 06:41 PM.
toddburch is offline   0 Reply With Quote
Old Jan 31, 2007, 07:46 PM   #4
bobber205
Thread Starter
macrumors 68020
 
bobber205's Avatar
 
Join Date: Nov 2005
Location: Oregon
Send a message via AIM to bobber205 Send a message via Yahoo to bobber205 Send a message via Skype™ to bobber205
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!!!!
bobber205 is offline   0 Reply With Quote
Old Jan 31, 2007, 08:09 PM   #5
toddburch
macrumors 6502a
 
Join Date: Dec 2006
Location: Katy, Texas
Send a message via AIM to toddburch Send a message via MSN to toddburch
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")
toddburch is offline   0 Reply With Quote
Old Jan 31, 2007, 09:25 PM   #6
bobber205
Thread Starter
macrumors 68020
 
bobber205's Avatar
 
Join Date: Nov 2005
Location: Oregon
Send a message via AIM to bobber205 Send a message via Yahoo to bobber205 Send a message via Skype™ to bobber205
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.
bobber205 is offline   0 Reply With Quote
Old Jan 31, 2007, 10:58 PM   #7
toddburch
macrumors 6502a
 
Join Date: Dec 2006
Location: Katy, Texas
Send a message via AIM to toddburch Send a message via MSN to toddburch
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.

Glad I could help.

Todd
toddburch is offline   0 Reply With Quote
Old Feb 1, 2007, 12:08 AM   #8
bobber205
Thread Starter
macrumors 68020
 
bobber205's Avatar
 
Join Date: Nov 2005
Location: Oregon
Send a message via AIM to bobber205 Send a message via Yahoo to bobber205 Send a message via Skype™ to bobber205
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!!!!
bobber205 is offline   0 Reply With Quote

Reply
MacRumors Forums > Apple Systems and Services > Programming > Mac Programming

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Similar Threads
thread Thread Starter Forum Replies Last Post
All iPads: Wow Factor sleepyking iPad 2 Oct 22, 2013 11:21 PM
Crop factor and lenses G.T. Digital Photography 16 Oct 17, 2013 05:05 PM
Two-Factor Authentication for Macs? doubledee Mac Basics and Help 8 May 20, 2013 08:26 PM
Anyone like the 4S form factor better than 5? bgro iPhone 36 Mar 4, 2013 11:39 AM

Forum Jump

All times are GMT -5. The time now is 02:42 AM.

Mac Rumors | Mac | iPhone | iPhone Game Reviews | iPhone Apps

Mobile Version | Fixed | Fluid | Fluid HD
Copyright 2002-2013, MacRumors.com, LLC