*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:

LetBelow is the sample source code on how it is implemented using the C programming languageaandbbe positive integers with a >= b. The following algorithm computes gcd(a,b) in a finite number of steps.

(1) Let r_{0}= a and r_{1}= b

(2) Set i = 1

(3) Divide r_{i-1}by r_{i}to get a quotient q_{i}and remainder r_{i+1}, r_{i-1}= r_{i}.q_{i}+ r_{i+1}with 0 <= r_{i+1}<= r_{i}

(4) If the remainder r_{i+1}= 0, then r_{i}=gcd(a,b) and the algorithm terminates.

(5) Otherwise, r_{i+1}> 0, so set i = i + 1 and go to Step 3.

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

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

## No comments:

## Post a Comment