Using Euclid Algorithm to find GCF(GCD)

Question

I am trying to write a function to find the gcd of 2 numbers, using Euclid's Algorithm which I found here.

From the larger number, subtract the smaller number as many times as you can until you have a number that is smaller than the small number. (or without getting a negative answer) Now, using the original small number and the result, a smaller number, repeat the process. Repeat this until the last result is zero, and the GCF is the next-to-last small number result. Also see our Euclid's Algorithm Calculator.
Example: Find the GCF (18, 27)
27 - 18 = 9
18 - 9 = 9
9 - 9 = 0
So, the greatest common factor of 18 and 27 is 9, the smallest result we had before we reached 0.

Following these instructions I wrote a function:

int hcf(int a, int b)
{
    int small = (a < b)? a : b;
    int big = (a > b)? a : b;
    int res;
    int gcf;

    cout << "small = " << small << "\n";
    cout << "big = " << big << "\n";

    while ((res = big - small) > small && res > 0) {
            cout << "res = " << res << "\n"; 
    }
    while ((gcf = small - res) > 0) {
        cout << "gcf = " << gcf << "\n";
    }


    return gcf;
}

However, the second loop seems to be infinite. Can anyone explain why?

I know the website actually shows the code(PHP), but I'm trying to write this code using only the instructions they give.

I mean stuff like while ((res = big - small) > small && res > 0). If you just look at this, it is not trivial to tell what the value of all your variables will be after the loop is done. That is a very bad thing! — Baum mit Augen
– Baum mit Augen ♦, Commented Feb 1, 2015 at 20:53
I'd suggest int gcd(int a, int b) { return b ? gcd(b, a%b) : a; } instead. Using subtraction just isn't a great idea. — tmyklebu
– tmyklebu, Commented Feb 1, 2015 at 20:58
What you try to implement is not Euclid's algorithm, it's actually way more inefficient, O(n) instead of O(log n) — Niklas B.
– Niklas B., Commented Feb 1, 2015 at 20:59

Barry · Accepted Answer · 2015-02-01 20:57:27Z

7

Of course this loop is infinite:

while ((gcf = small - res) > 0) {
    cout << "gcf = " << gcf << "\n";
}

small and res don't change in the loop, so gcf doesn't either. That loop is equivalent to:

gcf = small - res;
while (gcf > 0) {
    cout << "gcf = " << gcf << "\n";
}

which is probably more clear.

I would port that algorithm to code as follows:

int gcd(int a, int b) {
    while (a != b) {
        if (a > b) {
            a -= b;
        }
        else {
            b -= a;
        }
    }
    return a;
}

Although typically gcd is implemented using mod, since it's much faster:

int gcd(int a, int b) {
    return (b == 0) ? a : gcd(b, a % b);
}

answered Feb 1, 2015 at 20:57

Barry

312k32 gold badges736 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Using Euclid Algorithm to find GCF(GCD)

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related