Finding GCD using divison method in C

Question

So I wanted to write a function to calculate the Gcd or HCF of two numbers using the Divison method.This is my code:

#include <stdio.h>
#include <stdlib.h>

void gcd(int x, int y)
{
    int g,l;
    if (x >= y)
    {
        g = x;
        l = y;
    }

    else
    {
        g = y;
        l = x;
    }
    while (g % l != 0)
    {
        g = l;
        l = g % l;
    }

    printf("The GCD of %d and %d is %d", x, y, l);

}

int main(void)
{
    gcd(8, 3);

    return 0;
}

I am getting no output with this(error?): Process returned -1073741676 (0xC0000094)

Is there a problem with my loop?

Answer 1

First of all, take into account that you are exchanging the numbers when x >= y which means that you try to put in x the smaller of the two. For GDC, there's no need to do this, as the remainder of a division by a bigger number is always the original number, so if you have the sequence 3, 8, the first remainder will be 3, and the numbers switch positions automatically as part of the algorithm. So there's no need to operate with g (I guess for greater) and l (for lesser) so you can avoid that.

#include <stdio.h>
#include <stdlib.h>

void gcd(int x, int y)
{
    int g,l;
    if (x >= y)
    {
        g = x;
        l = y;
    }

    else
    {
        g = y;
        l = x;
    }

Then, in this second part (the loop part) you have to take into account that you are calculating g % l twice in the same loop run (this is not the Euclides' algorithm).

    while (g % l != 0)
    {
        g = l;
        l = g % l;
    }

You should better use a new variable r (for remainder, but I should recommend you to use longer, descriptive names) so you have always an idea of what the variable holds.

    int r;
    while ((r = g % l) != 0) {
        g = l;
        l = r;
    }

you see? I just do one division per loop, but you make a l = g % l; which modifies the value of l, making you go through two iterations of the loop in one.

The final program is:

#include <stdio.h>
#include <stdlib.h>

int gcd(int greater, int lower)
{
    int remainder;

    while ((remainder = greater % lower) != 0) {
        printf("g=%d, l=%d, r=%d\n", greater, lower, remainder);
        greater = lower;
        lower = remainder;
    }

    return lower; /* remember that remainder got 0 in the last loop */

}

int main(void)
{
    int x = 6, y = 8;

    printf("The GCD of %d and %d is %d\n",
            x, y, gcd(x, y));

    printf("The GCD of %d and %d is %d\n",
            y, x, gcd(y, x));

    return EXIT_SUCCESS;
}

(I have added a trace printf in the gcd() loop to show how the variables are changing, and both calculations ---changing the parameter values--- to show what I said above about the automatic change in order. Also, it's better to use the gcd() as a function that returns the value, and let main() decide if it wants to print results, or use the value for something else.

Enjoy it!! :)

Answer 2

I use this loop while to find the gcd of two numbers like this:

void gcd(int x, int y)
{
    int k=x,l=y;
    if(x>0&&y>0)
    {
        while(x!=0&&y!=0)
        {
           if(x>y)
           {
               x=x-y;
           }
           else
           {
               y=y-x;
           }
        }
    }
  printf("\nThe GCD of %d and %d is %d", k, l, x);
}
int main(void)
{
   gcd(758,306);
   return 0;
}

Examples:

Input:

x=758 , y=306

x=27 , y=45

x=3 , y=8

Output:

printf("\nThe GCD of 758 and 306 is 2");

printf("\nThe GCD of 27 and 45 is 9");

printf("\nThe GCD of 3 and 8 is 1");

Answer 3

In:

        g = l;
        l = g % l;

the assignment g = l loses the value of g before g % l is calculated. Change it to:

        int t = g % l;
        g = l;
        l = t;