Thursday, July 4, 2013

Greatest Common Divisor (Eucledian)

Greatest Common Divisor (GCD for short) is the largest positive integer that divides two numbers. In other words, the greatest common divisor of a and b is, as its name suggests, the largest positive integer d such that d | a and d | b. In this post, we will see how we can calculate GCD efficiently using an algorithm that is known as Eucledian Algorithm.

The key thing in this algorithm is division with remainder, which is simply the method of "long division" that you learned in elementary school. Thus if a and b are positive integers and if you attempt to divide a by b, you will get a quotient q and a reminder r.

Below is the theorem used for this algorithm:
Let a and b be positive integers with a >= b. The following algorithm computes gcd(a,b) in a finite number of steps.
(1) Let r0 = a and r1 = b
(2) Set i = 1
(3) Divide ri-1 by ri to get a quotient qi and remainder ri+1, ri-1 = ri.qi + ri+1 with 0 <= ri+1 <= ri
(4) If the remainder ri+1 = 0, then ri=gcd(a,b) and the algorithm terminates.
(5) Otherwise, ri+1 > 0, so set i = i + 1 and go to Step 3.
Below is the sample source code on how it is implemented using the C programming language

int gcd ( int number1 , int number2 )
    if ( number2 == 0 )
        return number1 ;
        return gcd ( number2 , number1 % number2 ) ;

Hope it helps anyone who needs it. Happy Programming :)

No comments:

Post a Comment