Menu
What's new
By:
Filters

Greatest Common Factor (GCF) Calculator

Status
Not open for further replies.
Iconoclast

Iconoclast

New member
I have decided to give up bypassing the use of the modulo function, while some conversions were of success. Instead, I have used tolerance of the function to make an engine that takes two integers the user enters and returns the greatest common factor (or GCF) of the two integers. This is one of my tougher experiments that took a lot of (tens of hours of) sitting down and writing numbers, especially the goddamn debugging.

An integer is a number with all decimal places past the decimal point 0. 72.00000... (72) is an integer. 72.0185 is not an integer. Keep in mind that this engine will only support integers. A factor is an integer that goes into another integer an integer amount of times.

Factors of 24 are: 1, 2, 3, 4, 6, 8, 12 and 24.
Factors of 32 are: 1, 2, 4, 8, 16, and 32.

The greatest common factor of these two integers therefore is 8. I have attached my current progress of the engine as an uncompressed zip archive.

One last thing. You can use this to return the aspect ratio of a resolution. Try 640 and 480. Once you enter these into the program, not only will the GCF be returned, but both these numbers will be divided by the GCF (160) to return the simplified ratio of 4:3.
 
smcd

smcd

Active member
This doesn't seem to work ;) The greatest common factor of 15 and 69 is not 9. (It should be 3?) Another example is one where there are no GCF, excluding 1... use 4 and 11, which says 3 is the GCF.

On a side note, you can use "strip -s GCF.exe" to remove the huge debugging info from the .exe you suppled - saves about 200kb

EDIT: here's a tool to find the factors of numbers http://www.apples4theteacher.com/prime-factors.html which might make debugging this easier
 
Last edited:
OP
Iconoclast

Iconoclast

New member
sethmcdoogle said:
This doesn't seem to work ;) The greatest common factor of 15 and 69 is not 9. (It should be 3?) Another example is one where there are no GCF, excluding 1... use 4 and 11, which says 3 is the GCF.

On a side note, you can use "strip -s GCF.exe" to remove the huge debugging info from the .exe you suppled - saves about 200kb

EDIT: here's a tool to find the factors of numbers http://www.apples4theteacher.com/prime-factors.html which might make debugging this easier
Click to expand...
Yes, I am already aware of this issue. In fact, I have been aware of it since I first came up with the current equation, y % x.

x = 9, y = 6

If x > y, equation will be x % y = GCF.
9 / 6 is 1 and a remainder of 3 (9 % 6 = 3). 3 is the GCF.

However, this equation will not always work. Sometimes, you need to use the equation x - (y % x), or y - (x % y), depending on whether the value of x is greater than or less than the value of y.

x = 7, y = 4
x % y = 7 % 4 = 3
y - (x % y) = 4 - (3) = 1

Now, my biggest question is, how the hell am I going to get my program to determine which equation to use? So far, it seems like I may have to declare a fourth variable, any integer i, where i != 0 and i != 1. I would like to avoid declaring another variable, so if anybody figures out a method, let me know. I of course will still be experimenting with this, while I am running out of time.

This is my current sourcecode on disk.

Code: 
#include <iostream>
using namespace std;
int main()
{
    int f, x, y; //Let x and y be integers and f the greatest common factor of x and y.
    cout<<"Enter the first integer:  "; //Asks for a value for x.
    cin>>x; //Gives a field for entering a value for x.
    cout<<"Enter the second integer:  "; //Asks for a value for y.
    cin>>y; //Gives a field for entering a value for y.
    //If both values are equal, then each value is the greatest common factor.
    if (x == y) {f = x = y;}
    else if (x < y) //If x is less than y...
    {
        if (y % x != x - (y % x)) {f = x - (y % x);} //Debugging line.
        //Let the remainder of y divided by x be the greatest common factor,
        //so long as this remainder is not 0.
        else if (y % x != 0) {f = y % x;}
        else if (y % x == 0) {f = x;} //Otherwise, let the greatest common factor be x.
    }
    else if (x > y) //If x is greater than y...
    {
        if (x % y != y - (x % y)) {f = y - (x % y);} //Debugging line.
        //Let the remainder of x divided by y be the greatest common factor,
        //so long as this remainder is not 0.
        else if (x % y != 0) {f = x % y;}
        else if (x % y == 0) {f = y;} //Otherwise, let the greatest common factor be y.
    }
    cout<<"\n\nThe greatest common factor is "<<f<<".\n"; //Types the greatest common factor on screen.
    //Types the simplified ratio of the first number to the second number.
    cout<<"The simplified ratio of the first number to the second number is "<<x / f<<":"<<y / f<<".\n\n";
    system("PAUSE"); //Pauses execution and waits for a press of a key before continuing towards termination.
}
On lines 13 and 18 is my experiemental method so far, which has not been of success.
 
Last edited by a moderator:
Garstyciuks

Garstyciuks

New member
Probably the best algorithm for finding GCF is called Euclidian algorithm and looks like this:

Code: 
int GCF(int a, int b)
{
	int t;
	while (b != 0)
	{
		t = b;
		b = a % b;
		a = t;
	}
	return a;
}

Without iteration you can't properly solve this problem. You would have infinte cases when you need to use different formulas for determining it.
 
OP
Iconoclast

Iconoclast

New member
Um...okay. Well, I managed to make a sad attempt of a C version out of that.

Code: 
#include <iostream>
int main()
{
    int GCF(int a, int b)
    {
        int t;
        while (b != 0)
        {
              t = b;
              b = a % b;
              a = t;
        }
        printf(GCF);
        return a;
    }
}
Truth being, I gave up learning C because I was overly confused about everything. Now that it's been months since, I should be able to understand it, and yet, my C tutorials were deleted. I would appreciate a C++ version of this code, for when I try to compile it in C, I get an error on line 1 saying "No such file or directory," and of course pointing to errors about the print function due to the failure to detect this header file, which is normally found using C++.
 
smcd

smcd

Active member
The code that Garstyciuks posted is valid both C and C++. Your code, however, is C++ mixed with C functionality - you should have
Code: 
#include<cstdio>
instead of iostream as you are using printf which is C I/O related but is also available in C++. If you do not understand C, I find it very odd if you can use C++ since they are very similar and if anything C++ is more complex than C.

For more information on Euclid's algorithm, try here http://en.wikipedia.org/wiki/Euclidean_algorithm I too suggest its use.
 
Garstyciuks

Garstyciuks

New member
Here's the complete code for you:

Code: 
#include <stdio.h>

int GCF(int a, int b)
{
	int t;
	while (b != 0)
	{
		t = b;
		b = a % b;
		a = t;
	}
	return a;
}

int main(int argc, char **argv)
{
	int a, b;
	printf("Input 2 numbers:\n");
	scanf("%i %i", &a, &b);
	printf("The GCF is %i\n", GCF(a,b));
	return 0;
}
 
Toasty

Toasty

Sony battery
Proper usage in C:
Code: 
#include <stdio.h>

int GCF(int a, int b);

int main(int argc, char** argv) {
	int gcf = GCF(24, 32);
	printf("%i\n", gcf);
	return 0;
}

int GCF(int a, int b) {
	int t;
	while (b != 0)
	{
		t = b;
		b = a % b;
		a = t;
	}
	return a;
}

The same also works in C++, but you also have the option of using the iostream library instead of stdio:
Code: 
#include <iostream>

using namespace std;

int GCF(int a, int b);

int main(int argc, char** argv) {
	int gcf = GCF(24, 32);
	cout << gcf << endl;
	return 0;
}

int GCF(int a, int b) {
	int t;
	while (b != 0)
	{
		t = b;
		b = a % b;
		a = t;
	}
	return a;
}

EDIT: Dang, sethmcdoogle and Garstyciuks beat me to the punch!
 
OP
Iconoclast

Iconoclast

New member
sethmcdoogle said:
The code that Garstyciuks posted is valid both C and C++. Your code, however, is C++ mixed with C functionality - you should have
Code: 
#include<cstdio>
instead of iostream as you are using printf which is C I/O related but is also available in C++. If you do not understand C, I find it very odd if you can use C++ since they are very similar and if anything C++ is more complex than C.

For more information on Euclid's algorithm, try here http://en.wikipedia.org/wiki/Euclidean_algorithm I too suggest its use.
Click to expand...
Yes, I have read that page already, and if I am linked to that thing one more time, it is only further rubbing it into me my failure.

Code: 
 [B]function[/B] gcd(a, b)
     [B]if[/B] b = 0 [B]return[/B] a
     [B]else[/B] [B]return[/B] gcd(b, a [B]mod[/B] b)
I mean, what the hell is that?
"The function of taking the greatest common denominator of two numbers is either returning a for this value if b has a value of 0 or otherwise it is returning the value of b and a mod b."

That is basically saying a = a % b.

GCD(a, b) = GCD(a mod b, b); b != 0

I didn't even know there was a GCF function built into the damn thing. All this time, I was just using algebraic equations.

Also, this??

Code: 
 [B]function[/B] gcd(a, b)
     [B]while[/B] b ≠ 0
         [B]if[/B] a > b
             a := a - b
         [B]else[/B]
             b := b - a
     [B]return[/B] a
You can't say a = a - b or b = b - a.

x = x - y
x = x + -y
-x, -x
0 = 0 + - y
-y = 0

You are basically forcing a value of 0 for b, while b cannot be 0. Such an equation has no real solution.

Also, about the whole C/C++ thing, I really honestly mean it when I say the C version just isn't getting to me right now. I hate the scanf(%blah, crap) method. If C++ be exponentially harder in future learnings, then so be it.

In the meantime, I obviously have a lot more reading to do. After two weeks, school will finally be at and end, and I will have extra time towards learning these codings you all have posted. For now, I know nothing more than if statements and basic functions.
 
smcd

smcd

Active member
No gcd/gcf function is "built in" to either C or C++.

If you look carefully at
Code: 
 function gcd(a, b)
     if b = 0 return a
     else return gcd(b, a mod b)
it swaps values each recursive call. Write each step of the recursion out using simple values (say 6 and 9 or so) and you should be able to follow it better.
 
OP
Iconoclast

Iconoclast

New member
sethmcdoogle said:
No gcd/gcf function is "built in" to either C or C++.
Click to expand...
Like I said before, I didn't know that. Course that doesn't apply now. I mean, I observed that by looking at Toasty's versions of the program in both C and C++.

If you look carefully at
Code: 
 function gcd(a, b)
     if b = 0 return a
     else return gcd(b, a mod b)
it swaps values each recursive call. Write each step of the recursion out using simple values (say 6 and 9 or so) and you should be able to follow it better.
Click to expand...
But why take the value of GCD(b, a % b) instead of just GCD(a, b) to get the damn GCD of both numbers? Is this some pointless delay?

Besides, GCD(6, 9) = 3. GCD(9, 6 % 9) = GCD(9, (2/3)) where two-thirds is not an integer.

Edit: ...0 and a remainder of 6, eh? Alright, then after analyzing several other examples, if GCD(a, b) = GCD(b, a % b) = GCD(a % b, b), then this concludes that a = a % b; b != 0.

6, 9
6 = 6 % ...I see your point now.

Still, you know, I'm just not catching on to what this is used for.
 
Last edited:
smcd

smcd

Active member
Recursion is tricky to wrap your head around... it takes some time. After you get used to it, some problems will become much more natural and easier to program. My previous example stepped out with recursion:

gcd(a,b)
...
gcd(6,9)

first pass, a=6, b=9
b is not 0, so call gcd(9, 6%9) // 6%9 = 6

second pass, a=9, b=6
b is not 0, so call gcd(3, 9%6) // 9%6 = 3

third pass, a=6, b=3
b is not 0, so call gcd(6, 6%3) // 6%3 = 0

fourth pass, a=3, b=0
b is zero, so return a (3)

EDIT: I messed up and there are actually 4 levels of recursion.
 
Last edited:
OP
Iconoclast

Iconoclast

New member
Well, first, I'm not getting the passes. Why are you writing three passes in which I fail to notice a transitional pattern between? What equation returns these new values for a and b through each step until b is 0?
 
smcd

smcd

Active member
Please note I made a mistake in the above post and edited it.

The recursive edition of the gcd does,
Code: 
 function gcd(a, b)
     if b = 0 return a
     else return gcd(b, a mod b)

the function only exits (returns) when b = 0. It calls itself until this condition is met. Below is a method that does each level of the function for you:

Code: 
#include<stdio.h>

int gcd(int a, int b)
{
	printf("a = %d, b = %d\r\n", a, b);
	if(b == 0)
		return a;
	else
		return gcd(b, a%b);
}

int main()
{
	printf("gcd(6,9) = %d\r\n", gcd(6, 9));
	return 0;
}

Results:
Code: 
a = 6, b = 9
a = 9, b = 6
a = 6, b = 3
a = 3, b = 0
gcd(6,9) = 3
 
OP
Iconoclast

Iconoclast

New member
If a = a % b, where b > a and b != 0, why can't you just say gcd(a, b) to return the direct GCD? What's with the delay? Changing it to gcd(b, a % b) hardly does anything except delay.

So maybe?

Code: 
#include <iostream>
using namespace std;
int main()
{
    int d, x, y; //Let x and y be integer variables and d their greatest common divisor.
    cin>>x;
    cin>>y;
    if (x == 0 == y) {
          cout<<"The greatest common divisor of 0 and 0 is theoretically infinity.";
          system("PAUSE");
          system("EXIT");
          }
    else if (x != y == 0) {d = x;}
    else if (y != x == 0) {d = y;}
    else if (y != 0 != x) {d = gcd(x, y);}
    cout<<d;
    system("PAUSE");
}
 
Last edited:
smcd

smcd

Active member
Ah, but each call of the function in recursion gets another copy of the variable(s) so it's a new instance of a and b. Maybe that's where you are getting confused?

You can change the printf("a = %d, b = %d\r\n", a, b); to printf("a (%X) = %d, b(%X) = %d\r\n", &a, a, &b, b); to see that the addresses are different. The compiler may complain or warn about unsigned values for the &a and &b but it should be safe to ignore these.
 
Last edited:
OP
Iconoclast

Iconoclast

New member
Well, what Dev-C++ is telling me, is that gcd is an undeclared variable. I need to figure out how to use it as a function. d = function gcd(x, y)? That doesn't make any sense...or, screwing algebraic properties, maybe you could say that.

Edit: GRRR at C version. Me no like C. C++ first. Go back to C later.
 
smcd

smcd

Active member
if you have the body of a function below main() you need to have a function prototype above main(). this applies for any function calling another function - it must be listed before the calling function, or there needs to be a function prototype so the compiler knows what is happening.
 
Status
Not open for further replies.

Top