Greatest Common Divisor

So we are trying to compute GCD ( Greatest Common Divisor) of two numbers, Say a and b.As the name suggests we are trying to determine the greatest number that divides both a and b.

Finding Procedure:
There are many procedures of how we can find the gcd of two numbers, but we will discuss about the euclidean method here.

It works on the principle GCD(a,b)=GCD(b,a%b). Since GCD(b,a%b) is a smaller state,it is easier to find than the original.So we can solve it using this recursion relation and using the base case, GCD(a,a)=a and GCD(a,0)=a;

Code:
Recursive version:
int gcd ( int a, int b )
{
    if(b==0) return a;
    return gcd(b,a%b);
}

Iterative Version:
int gcd ( int a , int b )
{
    while(!b)
    {
        a=a%b;
        swap(a,b)
     }
}

Built in version:
There is also a builtin version in C++ for finding GCD. ( __gcd(a,b) ).

What i use:
I use this as my template:
template< class T > T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
Proof:
We can imagine a grid a * b. We are trying to find the largest number x 
such that we can cover the whole grid using tiles of size x * x . 
And if the whole grid is to be covered by the square sized tiles so x
must be a divisor of both a and b. So we will try to choose x such that x
be the smaller number between a and b (say b). If we found that it is not
possible to cover the whole grid, there must be some remainder of the grid
which will be a%b. So the we will try the same method for a= b and b=a%b;




GCD texure: courtesy Wiki.


Complexity:
Well the complexity of this algorithm is kindaa tricky, My coach refers me to an answer of stack overflow. For now I am only giving the complexity of the answer.but as soon as i understand the proof the solution i will rewrite this portion.
The complexity of above algorithm is - O( log10(a) + log10(b) ).

Coding Pitfalls:
Well this is one of the great things i have learnt recently from my Coach.Though i used the algorithm for a long time i didn't know this pitfall.That is the algorithm only works for non negative numbers. So in case of negative numbers are concerned we can either send absolute value of the numbers or we can take the absolute value of the result.

Another thing is- notice that 
GCD(0,0)=0. It should be infinity. Also, if you try to work with the return value of GCD(0,0), then you might get RTE due to division by zero.