macOS Greatest Common Factor Nightmare

[bobber205]

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.

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;
}

 

[toddburch]

Ah, the 'ol Euclid Algorithm. Page 2 of the Art of Computer Programming.

# 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]

(umm... just finished dinner - Lasanga).

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

#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

 

[bobber205]

Hmm. Whenever the answer should be 2/3 this logic dies. Why?

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;
}

 

[toddburch]

It dies because you are using "divisor" logic. You don't need it. All you need is the numer, denom and remainder.

#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")

 

[bobber205]

Here's what I was trying to "follow"

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.

 

[toddburch]

Divisor:
1. a number by which another number, the dividend, is divided.

Or, the denominator.

Let m and n be the two integer values.

m=4, n=6. m is the dividend, n is the divisor.

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.

Save the divisor in m

m=n. m now equals 6.

and save the remainder in n.

n=r. n now equals 4.

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

 

[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.