Like Tree2Likes

Euclid method for solving GCD problem

This is a discussion on Euclid method for solving GCD problem within the C Programming forums, part of the General Programming Boards category; Hello, I am trying to use the Euclidean method for solving the GCD problem. However, I keep getting an infinite ...

  1. #1
    Registered User
    Join Date
    Jun 2013
    Posts
    27

    Euclid method for solving GCD problem

    Hello,

    I am trying to use the Euclidean method for solving the GCD problem. However, I keep getting an infinite loop. After I input num1 and num2, the program doesn't respond with anything and doesn't allow me to type anything either. Here is the code:

    Code:
    #include <stdio.h>
    #include "genlib.h"
    #include "simpio.h"
    
    
    main()
    {
          int num1, num2, rem, x, y;
           
          printf ("This program calculates the GCD of two numbers.\n");
          printf ("Enter the first number: ");
          num1 = GetInteger();
          printf ("Enter the second number: ");
          num2 = GetInteger();
          x = num1;
          y = num2;
          rem=(num1%num2);
          while (rem != 0)
          {
                rem == num1 % num2;
                if (rem == 0)
                {
                    printf ("The GCD of %d and %d is %d", x, y, num2);
                }
                else
                {
                    num1 == num2;
                    num2 == rem;
                 }
            }
          getchar();
    }

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,459
    For future reference:
    Code:
    $ make gcd
    gcc -Wall -ggdb3 -std=c99 -o gcd gcd.c -lm
    gcd.c:2:20: fatal error: genlib.h: No such file or directory
    compilation terminated.
    It helps to provide us with all the necessary .c and .h files to test your program. That's easy to fix though, which leads me to:
    Code:
    $ make gcd
    gcc -Wall -ggdb3 -std=c99 -o gcd gcd.c -lm
    gcd.c:6:1: warning: return type defaults to ‘int’ [enabled by default]
    gcd.c: In function ‘main’:
    gcd.c:20:5: warning: statement with no effect [-Wunused-value]
    gcd.c:27:7: warning: statement with no effect [-Wunused-value]
    gcd.c:28:7: warning: statement with no effect [-Wunused-value]
    It's int main(void) and return an int at the end, usually 0 or EXIT_SUCCESS (defined in <stdlib.h>).

    As for the other 3 errors, note the difference between = for assignment, and == for comparison. Make sure you're using the right one in each case.
    Salem likes this.

  3. #3
    Registered User
    Join Date
    Jun 2013
    Posts
    27
    Quote Originally Posted by anduril462 View Post
    For future reference:
    Code:
    $ make gcd
    gcc -Wall -ggdb3 -std=c99 -o gcd gcd.c -lm
    gcd.c:2:20: fatal error: genlib.h: No such file or directory
    compilation terminated.
    It helps to provide us with all the necessary .c and .h files to test your program. That's easy to fix though, which leads me to:
    Code:
    $ make gcd
    gcc -Wall -ggdb3 -std=c99 -o gcd gcd.c -lm
    gcd.c:6:1: warning: return type defaults to ‘int’ [enabled by default]
    gcd.c: In function ‘main’:
    gcd.c:20:5: warning: statement with no effect [-Wunused-value]
    gcd.c:27:7: warning: statement with no effect [-Wunused-value]
    gcd.c:28:7: warning: statement with no effect [-Wunused-value]
    It's int main(void) and return an int at the end, usually 0 or EXIT_SUCCESS (defined in <stdlib.h>).

    As for the other 3 errors, note the difference between = for assignment, and == for comparison. Make sure you're using the right one in each case.
    It would be helpful if you could tell me where I have gone wrong with the = sign since I can't figure it out.

    Thanks

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,459
    The errors tell you line numbers where the compiler things you may have mixed up = and ==. However, a general rule of thumb when you're starting out is == should only be used in conditional stuff: if/else conditions and loop conditions. Also, especially when you're starting out, = should rarely, if ever be used inside a conditional.

    Note, if your compiler isn't warning you about those lines, then turn the warning level up to the maximum.

    EDIT:
    To explain the error message "statement with no effect", what the compiler is saying is "lines 20, 27 and 28 don't actually do anything". It's as if you just typed
    rem;
    Nothing useful actually happens in that statement. Comparing two numbers in and of it self produces a result (true or false, depending on whether they're equal), but if that result is not stored any where, not used as part of some larger expressions/calculation, and no branch or loop uses it's result to determine program flow, then the comparison is pointless.
    Last edited by anduril462; 06-28-2013 at 12:55 PM.

  5. #5
    Registered User
    Join Date
    Jun 2013
    Posts
    27
    Quote Originally Posted by anduril462 View Post
    The errors tell you line numbers where the compiler things you may have mixed up = and ==. However, a general rule of thumb when you're starting out is == should only be used in conditional stuff: if/else conditions and loop conditions. Also, especially when you're starting out, = should rarely, if ever be used inside a conditional.

    Note, if your compiler isn't warning you about those lines, then turn the warning level up to the maximum.

    EDIT:
    To explain the error message "statement with no effect", what the compiler is saying is "lines 20, 27 and 28 don't actually do anything". It's as if you just typed
    rem;
    Nothing useful actually happens in that statement. Comparing two numbers in and of it self produces a result (true or false, depending on whether they're equal), but if that result is not stored any where, not used as part of some larger expressions/calculation, and no branch or loop uses it's result to determine program flow, then the comparison is pointless.
    I don't think this is the problem. Even after playing around with the equal signs, the program doesn't solve. For example, I enter 49 for the first number and 35 for num2 and it won't give me an answer. It just gives a blank space. Then I press enter and the program ends and the window shuts down.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,459
    Quote Originally Posted by hockeybro12 View Post
    I don't think this is the problem. Even after playing around with the equal signs, the program doesn't solve. For example, I enter 49 for the first number and 35 for num2 and it won't give me an answer. It just gives a blank space. Then I press enter and the program ends and the window shuts down.
    Oh, but I think it is. But post your current program, after the changes. Maybe you introduced some other bug.

  7. #7
    Registered User
    Join Date
    Jun 2013
    Posts
    27
    Quote Originally Posted by anduril462 View Post
    Oh, but I think it is. But post your current program, after the changes. Maybe you introduced some other bug.


    Code:
    
    #include <stdio.h>
    #include "genlib.h"
    #include "simpio.h"
    
    
    main()
    {
          int num1, num2, rem, x, y;
           
          printf ("This program calculates the GCD of two numbers.\n");
          printf ("Enter the first number: ");
          num1 = GetInteger();
          printf ("Enter the second number: ");
          num2 = GetInteger();
          x = num1;
          y = num2;
          rem=(num1%num2);
          while (rem != 0)
          {
                rem = num1 % num2;
                if (rem = 0)
                {
                    printf ("The GCD of %d and %d is %d", x, y, num2);
                }
                else
                {
                    num1 = num2;
                    num2 = rem;
                }
        	}
          getchar();
    }

  8. #8
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Code:
    if (rem == 0)
    Kurt

  9. #9
    Registered User
    Join Date
    Jun 2013
    Posts
    66
    Compare and contrast the code you posted with the following. Note the use of == instead of =, that is what anduril462 is probably looking at:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int main(void)
        {
        int num1, num2, rem, x, y;
    
        printf ("This program calculates the GCD of two numbers.\n");
    
        printf ("Enter the first number: ");
        fflush(stdout);
        scanf("%d", &num1);
    
        printf ("Enter the second number: ");
        fflush(stdout);
        scanf("%d", &num2);
    
        x = num1;
        y = num2;
        rem = (num1 % num2);
    
        while (rem != 0)
            {
            rem = num1 % num2;
    
            if (rem == 0) /* Take special note here! */
                {
                printf ("The GCD of %d and %d is %d\n", x, y, num2);
                }
            else
                {
                num1 = num2;
                num2 = rem;
                }
            }
    
        getchar();
    
        return EXIT_SUCCESS;
        }

  10. #10
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,459
    I told you, you need to compile with the warning level set to the maximum:
    Code:
    $ make gcd
    gcc -Wall -ggdb3 -std=c99 -o gcd gcd.c -lm
    gcd.c: In function ‘main’:
    gcd.c:21:5: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    If you don't know how to do that, read the documentation, or ask on a forum (preferably one dedicated to said compiler, but this forum would be fine in this case). If your compiler doesn't warn you about such stuff, consider upgrading to something better.

    As for your problem, you went a little too far with fixing the = and == bit. There were three lines that were problematic, but you changed four lines. And you didn't pay attention to the rules of thumb I gave you, which would have tipped you off when you went to modify that fourth line.
    Salem likes this.

  11. #11
    Registered User
    Join Date
    Jun 2013
    Posts
    27
    Quote Originally Posted by ZuK View Post
    Code:
    if (rem == 0)
    Kurt
    I think this fixed part of the problem but now when I use 180 and 60 it doesn't work.

    Code:
    
    #include <stdio.h>
    #include "genlib.h"
    #include "simpio.h"
    
    
    main()
    {
          int num1, num2, rem, x, y;
           
          printf ("This program calculates the GCD of two numbers.\n");
          printf ("Enter the first number: ");
          num1 = GetInteger();
          printf ("Enter the second number: ");
          num2 = GetInteger();
          x = num1;
          y = num2;
          rem=(num1%num2);
          while (rem != 0)
          {
                rem = num1 % num2;
                if (rem == 0)
                {
                    printf ("The GCD of %d and %d is %d", x, y, num2);
                }
                else
                {
                    num1 = num2;
                    num2 = rem;
                }
        	}
          getchar();
    }

  12. #12
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,459
    Your algorithm is a little off. Take a look at the first implementation here: https://en.wikipedia.org/wiki/Euclid...mplementations.
    Code:
    function gcd(a, b)
        while b ≠ 0
           t := b
           b := a mod t
           a := t
        return a
    Where := is used for assignment, same as a single = in C.

    You are using num1 as a, num2 as b and rem as t. The names are irrelevant, but notice, they use b != 0 (num2 != 0) as the stopping condition. Also, they use a (num1) as the GCD. I would also recommend you change your code to remove the if/else inside the loop and just put the printf after the loop:
    Code:
    while (num2 != 0)
    {
        // calculations like the the above example, no if/else
    }
    printf("The GCD of %d and %d is %d\n", x, y, num1);  // note the \n at the end of the printf, it helps make the output of your program more legible

  13. #13
    Registered User
    Join Date
    Jun 2013
    Posts
    27
    Quote Originally Posted by anduril462 View Post
    Your algorithm is a little off. Take a look at the first implementation here: https://en.wikipedia.org/wiki/Euclid...mplementations.
    Code:
    function gcd(a, b)
        while b ≠ 0
           t := b
           b := a mod t
           a := t
        return a
    Where := is used for assignment, same as a single = in C.

    You are using num1 as a, num2 as b and rem as t. The names are irrelevant, but notice, they use b != 0 (num2 != 0) as the stopping condition. Also, they use a (num1) as the GCD. I would also recommend you change your code to remove the if/else inside the loop and just put the printf after the loop:
    Code:
    while (num2 != 0)
    {
        // calculations like the the above example, no if/else
    }
    printf("The GCD of %d and %d is %d\n", x, y, num1);  // note the \n at the end of the printf, it helps make the output of your program more legible
    In this situation, I do not understand what mod means. I input it as meaning % but this is not accurate. The program comes up with an error after inputing 49 and 35 and says .exe has stopped working.

    Code:
    #include <stdio.h>
    #include "genlib.h"
    #include "simpio.h"
    
    
    main()
    {
          int num1, num2, rem, x, y;
           
          printf ("This program calculates the GCD of two numbers.\n");
          printf ("Enter the first number: ");
          num1 = GetInteger();
          printf ("Enter the second number: ");
          num2 = GetInteger();
          x = num1;
          y = num2;
          rem=(num1%num2);
          while (rem != 0)
          {
                
                rem=num2;
                num2=num1%rem;
                num1=rem;
        	}
        	printf("The GCD of %d and %d is %d",x,y,num1);
          getchar();
    }
    Last edited by hockeybro12; 06-28-2013 at 02:11 PM.

  14. #14
    Registered User
    Join Date
    Jun 2013
    Posts
    66
    Quote Originally Posted by hockeybro12 View Post
    In this situation, I do not understand what mod means.
    mod means modulo. In C you can get a similar effect with the remainder operator (%).

  15. #15
    Registered User
    Join Date
    Jun 2013
    Posts
    27
    Quote Originally Posted by sonjared View Post
    mod means modulo. In C you can get a similar effect with the remainder operator (%).
    I have edited my previous post.

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

Similar Threads

  1. Replies: 12
    Last Post: 01-21-2013, 10:12 AM
  2. Replies: 2
    Last Post: 01-06-2013, 06:49 AM
  3. Simplifying Numerical Solving before actual solving
    By Vespasian in forum Tech Board
    Replies: 3
    Last Post: 10-14-2012, 11:39 AM
  4. GCD using the euclid method.
    By PYROMANIAC702 in forum C Programming
    Replies: 18
    Last Post: 07-23-2011, 09:46 PM
  5. need for a solving method
    By braddy in forum C++ Programming
    Replies: 8
    Last Post: 08-26-2006, 11:36 AM

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