Like Tree5Likes

GCD using the euclid method.

This is a discussion on GCD using the euclid method. within the C Programming forums, part of the General Programming Boards category; I have an assignment to use the euclid method to solve the GCD of two integers. Here is what I ...

  1. #1
    Registered User
    Join Date
    Jul 2011
    Posts
    51

    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. #2
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    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. #3
    Registered User
    Join Date
    Jul 2011
    Posts
    51
    Quote Originally Posted by CommonTater View Post
    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.

  4. #4
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Post your new code... please...

  5. #5
    Registered User
    Join Date
    Jul 2011
    Posts
    51
    Quote Originally Posted by CommonTater View Post
    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();
          }

  6. #6
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    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.
    Last edited by CommonTater; 07-23-2011 at 06:23 AM.

  7. #7
    Registered User
    Join Date
    Jul 2011
    Posts
    51
    Quote Originally Posted by CommonTater View Post
    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. #8
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    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. #9
    Registered User
    Join Date
    Jul 2011
    Posts
    51
    Quote Originally Posted by CommonTater View Post
    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. #10
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    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. #11
    Charming Registered User
    Join Date
    May 2011
    Posts
    49
    Quote Originally Posted by PYROMANIAC702 View Post
    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.
    Last edited by ardavirus; 07-23-2011 at 09:16 AM.
    If you are the smartest person in the room, you are in the wrong room.

  12. #12
    Registered User
    Join Date
    May 2009
    Posts
    2,765
    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.
    Last edited by stahta01; 07-23-2011 at 10:04 AM.

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by ardavirus View Post
    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.)
    Char*Pntr likes this.

  14. #14
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    Pyro - We have been through this many times before. Take the advice you are given, if you don't understand it then ask.

    Quote Originally Posted by PYROMANIAC702 View Post
    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"

    Quote Originally Posted by PYROMANIAC702 View Post
    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.
    stahta01 likes this.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  15. #15
    Charming Registered User
    Join Date
    May 2011
    Posts
    49
    Quote Originally Posted by tabstop View Post
    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.
    If you are the smartest person in the room, you are in the wrong room.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Euclid gcd
    By jimjohnson in forum C++ Programming
    Replies: 1
    Last Post: 05-26-2011, 11:30 PM
  2. Euclid Algorithm (extended)
    By nacho4d in forum C Programming
    Replies: 13
    Last Post: 12-07-2006, 02:56 AM
  3. Euclid's game.
    By InvariantLoop in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 01-31-2005, 05:13 PM
  4. Euclid Algorithm
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 07-01-2002, 11:27 PM
  5. Euclid's algorithm
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 10-03-2001, 11:59 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21