# Thread: GCD using the euclid method.

1. ## GCD using the euclid method.

I have an assignment to use the euclid method to solve the GCD of two integers. Here is what I have so far:

Code:
```#include <stdio.h>
#include "genlib.h"
#include "simpio.h"

main()

{
int num1, num2, rem, GCD;

printf ("This program calculates the GCD of two numbers.\n\n");
printf ("Enter the first number: ");
num1 = GetInteger();
printf ("Enter the second number: ");
num2 = GetInteger();
while (rem != 0)
{
if (rem == 0)
{
GCD = num2;
printf ("The GCD of %d and %d is %d", num1, num2, num2);
}
if (rem != 0)
{
num1 = num2;
num2 = rem;
}
}
getchar();
}```
When I compile it, the program never gives me a solution, which means it's running an infinite loop and I can't figure out how to stop it.

2. You never calculate rem (the exit condition of your loop) and you are using the variable without first assigning it a value.

Moreover; you never actually calculate the greatest common denominator... you just assign num1 to equal num2 then num 2 to equal the uninitialized (random) value of rem.

3. Originally Posted by CommonTater
You never calculate rem (the exit condition of your loop) and you are using the variable without first assigning it a value.

Moreover; you never actually calculate the greatest common denominator... you just assign num1 to equal num2 then num 2 to equal the uninitialized (random) value of rem.
I should have clarified, GCD is Greatest Common Divisor. Anyways, after assigning rem (remainder) to num1 % num2, it is still an infinite loop.

5. Originally Posted by CommonTater
Code:
```#include <stdio.h>
#include "genlib.h"
#include "simpio.h"

main()

{
int num1, num2, rem, GCD;

printf ("This program calculates the GCD of two numbers.\n\n");
printf ("Enter the first number: ");
num1 = GetInteger();
printf ("Enter the second number: ");
num2 = GetInteger();
rem = num1 % num2;
while (rem != 0)
{
if (rem == 0)
{
GCD = num2;
printf ("The GCD of %d and %d is %d", num1, num2, num2);
}
if (rem != 0)
{
num1 = num2;
num2 = rem;
}
}
getchar();
}```

6. Your loop is still not changing the values...

First time through .. num1 = num2 ... your first user value is now lost.... num2 = rem now your second user value is lost.
Second time through num1 = num2 ... both num1 and num2 now = rem. num2 = rem ... no change.

Inside your loop you are not calculating a greatest common denominator... you are simply wiping out your input variables.

Thing is it doesn't look like you actually understand the problem or how to solvie it.. Can you work GCD with nothing but paper and pencil? If not then you need to get that sorted first. Then once you know how to solve the problem you can code it in C... No programmer, no matter how clever or experienced can ever code the solution to a problem he does not understand.

7. Originally Posted by CommonTater
Your loop is still not changing the values...

First time through .. num1 = num2 ... your first user value is now lost.... num2 = rem now your second user value is lost.
Second time through num1 = num2 ... both num1 and num2 now = rem. num2 = rem ... no change.

Inside your loop you are not calculating a greatest common denominator... you are simply wiping out your input variables.
That is exactly what the assignment tells me to do... It tells me to assign num2 to num1 and assign rem to num2, then loop, so when rem = 0, the loop terminates. Also it's not denominator, it's divisor. I could easily change the second if to an else, but that won't change anything.

8. The assignment is telling you to use the Euclidian method to find the Greatest Common Denominator of two numbers.

This is a calculation...
You aren't doing any calculations.

Euclidean algorithm - Wikipedia, the free encyclopedia

9. Originally Posted by CommonTater
The assignment is telling you to use the Euclidian method to find the Greatest Common Denominator of two numbers.

This is a calculation...
You aren't doing any calculations.

Euclidean algorithm - Wikipedia, the free encyclopedia
Since the larger of the two numbers is reduced, repeating this process gives successively smaller numbers until one of them is zero.
That is exactly what I am doing. Also, for the third time, it's greatest common DIVISOR! Please correct me if i'm wrong, but my code seems to be doing exactly that. If not, could you post some code that will work?

10. Nope... I won't hand it to you... this is your problem to figure out. It's your homework, not mine.

Learn how to do the Euclidean algorithm on paper, step by step.
Literally get a piece of paper and solve it longhand...
If you can't do that, you do not understand the problem.
If you do not understand the problem, you cannot hope to solve it.

Your loop performs no math on either input variable, it simply moves rem into both your input variables and then runs on forever.

Here's a hint.... Somplace in that loop you need to use both - and % to solve the problem...

11. Originally Posted by PYROMANIAC702
Also, for the third time, it's greatest common DIVISOR!
Also known as greatest common factor or greater common denominator or highest common factor or greatest common measure.

12. Sentinel value - Wikipedia, the free encyclopedia

A simple loop uses a single (non volatile) Sentinel Value to terminate the loop.

Things to watch out for (examples of poor logic). I could only think of one; but, there is likely more.

• The Sentinel Value never changes inside the loop; this can cause an endless loop or one that never runs (or just runs once in a do while loop)

The fix is either change the choice of the Sentinel Value or add code to modify the value of the Sentinel Value inside the loop.

Edit: The above is just restating Common Tater logic in new words.
Edit: "non volatile" variables are variables NOT changed by logic outside the normal program.

Tim S.

13. Originally Posted by ardavirus
Also known as greatest common factor or greater common denominator or highest common factor or greatest common measure.
GCD could never be greatest common denominator, since "greatest common denominator" does not exist as a thing. (There is least common denominator, but that's rather different.)

14. Pyro - We have been through this many times before. Take the advice you are given, if you don't understand it then ask.

Originally Posted by PYROMANIAC702
That is exactly what I am doing..... Please correct me if i'm wrong, but my code seems to be doing exactly that.
Ok, you are wrong. If that is exactly what you were doing, you would be getting the correct answer. Instead you just created an infinite loop. I am pretty sure the assignment doesn't say "Create a program which makes and infinite loop and doesn't solve any problems"

Originally Posted by PYROMANIAC702
If not, could you post some code that will work?
As you have been told on your other threads, no one will do your homework for you. As a reminder, here is our homework policy. Now since I know you are not a fan of reading, I took the liberty to look at the wiki site Tater so graciously posted for you and I found this little hidden gem:
Code:
```function gcd(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a```
Now since I know you don't do functions just ignore the first and last line. In fact since I know you aren't a fan of reading let me post this as:
Code:
```while b ≠ 0
t := b
b := a mod b
a := t```
So, if that is a while loop that does something, let's look at your while loop:
Code:
``` while (rem != 0)
{
if (rem == 0)
{
GCD = num2;
printf ("The GCD of %d and %d is %d", num1, num2, num2);
}
if (rem != 0)
{
num1 = num2;
num2 = rem;
}
}```
Can you spot a difference? Also it would be nice of you fixed your indentation.

15. Originally Posted by tabstop
GCD could never be greatest common denominator, since "greatest common denominator" does not exist as a thing. (There is least common denominator, but that's rather different.)
I stand corrected, thanks for pointing that out tabstop. I have to remind myself that google is not telling the truth all the time.

Popular pages Recent additions