Greatest Common Divisor

Greatest Common Divisor(GCD) of two numbers, as the name suggests is the biggest number that divides both the numbers without leaving any remainder i.e. perfect division.

Take 10 and 15 for example. The biggest number that perfectly divides both of them is 5 (common sense).

We can easily say that -:

GCD(a, 0) = a      (0 is perfectly divisible by any number)

GCD(a, a) = a

GCD(a, n*a) = a

Suppose GCD(a, b) = x. Looking at GCD from a different angle, we can say that both a and b are multiples of x.

Lets say that both a and b are non-negative integers and a >= b. We can write the following two equations -:

b = n*x where n >= 0

a = (n+k)*x where k >= 0

Methods to calculate GCD

  • Naive method – By the definition of GCD we can deduce that GCD(a, b) <= min(a, b) {provided one of them is not 0}. So, we can start an iterator from min(x, y) and get down to 1 checking for the remainder when both the numbers are divided by the iterator.


int gcd(int x, int y)
{
if(x*y == 0)
return (x==0)? y : x;
for(i = min(x, y); i>0; i--)
{
if(x % i == 0 && y % i ==0)
return i;
}
}

  • Euclid’s algorithm

Let GCD(a, b) = x (a and b are both non-negative and a>=b)

a%x = 0

b%x = 0

What about (a+b)%x?

Since a and b are both perfectly divisible by x, so is a + b, and so is a*m + b*n.

(a*m + b*n)%x = 0

So, take the case when m = 1 and n = -1.

(a – b)%x = 0 i.e. GCD(a, b) perfectly divides the difference between a and b.

a – b < a    (a and b are both non-negative and a>=b). By the definition of Greatest Common Divisor, it is the largest number that divides both the numbers perfectly. GCD(a, b) perfectly divides (a – b), a number lesser than a. For GCD(a, b) to perfectly  divide a – b, a – b will have to be a multiple of GCD(a, b). So, a can be replaced by a – b, without affecting the GCD.

GCD(a, b) = GCD(a – b , b)

This is the base on which Euclid’s algorithm stands.

The numbers can be reduced further by calling GCD with proper arguments (second argument <= first argument) until one of the arguments becomes zero. At that point return the non-zero argument which will be the GCD.

int gcd(int a, int b)
{
if(b == 0)
return b;
if(a < b)
return gcd(b, a);
return gcd(a-b, b);
}

So, we are calling the same function with the difference of the numbers as one of the arguments. Suppose a is quite large, then it will take quite a few calls of gcd to reach the point when the numbers will be swapped (when b becomes greater than a). Can we get to that point quickly? When will b become greater than a?

Suppose

a = k*b + l    (0 <= l < b)

So k*b will have to be subtracted from a to make it smaller than l, which is itself smaller than b. Before the swap of the arguments occurs the call to gcd will look like gcd(l, b).

The above equation if of the form

Dividend = Divisor*Quotient + Remainder

We can calculate the remainder directly and avoid the extra calls.

a%b will give us the remainder directly. Look at the code below

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

The call gcd(b, a%b) gets all the work done. If b>a the call directly gets to the point when a becomes smaller than b by continuous subtraction of b from a and then function is called with swapped arguments. If a>b, the function calls re-aligns the parameters so first argument is larger than second (a%b = a when b < a).

Advertisements

One thought on “Greatest Common Divisor

  1. Pingback: Crammer’s Edition – Maths for Computing | Nitemice

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s