Question

How to write Euclid's GCD non-recursive algorithm? Sample C/C++ code would be a great help.

Answer 1

Both Recursive and Non Recursive code

Greatest Common Divisor (GCD) C++ Program

One of the most useful math function is Greatest Common Divisor (GCD), also known as Highest Common Factor (HCF). It takes 2 (or more) integers (positive or negative, but not zero) and returns the largest positive integer which divides the input integers without leaving remainder.

Examples

• GCD(2, 4) = 2 because 2 divides both 2 and 4, and there is no other integer bigger than 2 which can do this.
• GCD(16, 24) = 8
• GCD(5, 6) = 1
• GCD(-2, 6) = 2

There are several ways to compute GCD as given on Wikipedia page, but we will use Euclid's algorithm, which is well suited for programming.

Note - Take care that the arguments are positive integers only. You can call GCD(abs(a), abs(b)) to ensure the negative integers are converted to positive.

The recursive version of Euclid's GCD function in C/C++

int gcd(int a, int b)
{
    if (b == 0) {
        return a;
    }
    else {
        return gcd(b, a % b);
    }
}

The non-recursive version of Euclid's GCD function in C/C++

int gcd(int a, int b)
{
    int c;
    while (b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

Let's trace GCD(18, 88) to see how code works for recursive version-

GCD(18, 88) => GCD(88, 18) => GCD(18, 16) => GCD(16, 2) => GCD(2, 0) => 2