GCD (Greatest Common Divisor)

Using Euclid's algorithm

A much more efficient method is the Euclidean algorithm, which uses a division algorithm such as long division in combination with the observation that the gcd of two numbers also divides their difference. To compute gcd(48,18), divide 48 by 18 to get a quotient of 2 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd. Note that we ignored the quotient in each step except to notice when the remainder reached 0, signalling that we had arrived at the answer. Formally the algorithm can be described as:

${\displaystyle \gcd(a,0)=a}$

${\displaystyle \gcd(a,b)=\gcd(b,a\,\mathrm {mod} \,b)}$,

where

${\displaystyle a\,\mathrm {mod} \,b=a-b\left\lfloor {a \over b}\right\rfloor }$.

If the arguments are both greater than zero then the algorithm can be written in more elementary terms as follows:

${\displaystyle \gcd(a,a)=a}$,

${\displaystyle \gcd(a,b)=\gcd(a-b,b)\quad ,}$ if a > b

${\displaystyle \gcd(a,b)=\gcd(a,b-a)\quad ,}$ if b > a

int gcd ( int a, int b ) {

    if ( b == 0 )
       return a;

    return  
       gcd ( b, a % b );

}

Binary method

An alternative method of computing the gcd is the binary gcd method which uses only subtraction and division by 2. In outline the method is as follows: Let a and b be the two non negative integers. Also set the integer d to 0. There are five possibilities:

• a = b.

This case is the base case.When a = b then return a and exit cause gcd(a,a)=a.

• Both a and b are even.

In this case 2 is a common divisor. Divide both a and b by 2, increment d by 1 to record the number of times 2 is a common divisor and continue.

• a is even and b is odd.

In this case 2 is not a common divisor. Divide a by 2 and continue.

• a is odd and b is even.

As in the previous case 2 is not a common divisor. Divide b by 2 and continue.

• Both a and b are odd.
  * If a>b then a = (a-b)/2  and continue
  * If a<b then b = (b-a)/2 and continue

Input: a, b positive integers
Output: g and d such that g is odd and gcd(a, b) = g×2d
    d := 0
    while a and b are both even do
        a := a/2
        b := b/2
        d := d + 1
    while a ≠ b do
        if a is even then a := a/2
        else if b is even then b := b/2
        else if a > b then a := (a – b)/2
        else b := (b – a)/2
    g := a
    output g, d 

Example: (a, b, d) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 6, 1) → (3, 3, 1) ; the original gcd is thus 2^d = 2¹ times a= b= 3, that is 6.

${\displaystyle O((\log a+\log b)^{2})}$Complexity : .

Sample Code:

unsigned int gcd(unsigned int u, unsigned int v)
{
    // simple cases (termination)
    if (u == v)
        return u;

    if (u == 0)
        return v;

    if (v == 0)
        return u;

    // look for factors of 2
    if (~u & 1) // u is even
    {
        if (v & 1) // v is odd
            return gcd(u >> 1, v);
        else // both u and v are even
            return gcd(u >> 1, v >> 1) << 1;
    }

    if (~v & 1) // u is odd, v is even
        return gcd(u, v >> 1);

    // reduce larger argument
    if (u > v)
        return gcd((u - v) >> 1, v);

    return gcd((v - u) >> 1, u);
}

In Cpp there is a built-in function for gcd.
__gcd(a,b).

From : Wikipedia