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

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.

Originally Posted by anduril462

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

Originally Posted by anduril462

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.

Originally Posted by hockeybro12

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.

Originally Posted by anduril462

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

Code:

if (rem == 0)

Kurt

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

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.

Originally Posted by ZuK

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

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

Originally Posted by hockeybro12

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

Originally Posted by sonjared

mod means modulo. In C you can get a similar effect with the remainder operator (%).

I have edited my previous post.