GCD using the euclid method.

**PYROMANIAC702** · 07-23-2011

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.

**~~CommonTater~~** · 07-23-2011

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.

**PYROMANIAC702** · 07-23-2011

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.

**~~CommonTater~~** · 07-23-2011

Post your new code... please...

**PYROMANIAC702** · 07-23-2011

Originally Posted by CommonTater

Post your new code... please...

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

**~~CommonTater~~** · 07-23-2011

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.

**PYROMANIAC702** · 07-23-2011

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.

**~~CommonTater~~** · 07-23-2011

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

**PYROMANIAC702** · 07-23-2011

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?

**~~CommonTater~~** · 07-23-2011

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

**ardavirus** · 07-23-2011

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.

**stahta01** · 07-23-2011

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.

**tabstop** · 07-23-2011

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

**AndrewHunter** · 07-23-2011

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.

**ardavirus** · 07-23-2011

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.

Thread: GCD using the euclid method.

Thread Tools

Search Thread

Display

GCD using the euclid method.

Similar Threads

Euclid gcd

Euclid Algorithm (extended)

Euclid's game.

Euclid Algorithm

Euclid's algorithm