Finding GCD (Euclidean Algorithm)

The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20.

The divisors of 12 are 1, 2, 3, 4, 6, 12
The divisors of 20 are 1, 2, 4, 5, 10 20

The highest number among the common divisors of 12 and 20 is 4. The gcd of 12 and 20 is 4. We'll start finding our answer by taking minimum of 12 and 20 which is 12. We'll return the highest number between 12 and 1 which is divided by 12 and 20. The steps are given below:

Is 12 divided by 12 and 20? No, decrement 12 by 1 which is 11
Is 11 divided by 12 and 20? No, decrement 11 by 1 which is 10
Is 10 divided by 12 and 20? No, decrement 10 by 1 which is 9
......................................................................................................
......................................................................................................
Is 5 divided by 12 and 20? No, decrement 5 by 1 which is 4
Is 4 divided by 12 and 20? Yes, we return 4 as our answer.

The implementation of the above algorithm is -

public int gcd(int a, int b) {
                      	for(int div = minimum(a, b); div >= 1; --div) {
                      		if(a % div == 0 && b % div == 0) {
                      			return div;
                      		}
                      	}
                      }

Open in new window

Let's consider two other numbers 540 and 600 and find their gcd.

The divisors of 540 are 1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 27, 30, 36, 45, 54, 60, 90, 108, 135, 180, 270, 540
The divisors of 600 are 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24 25, 30, 40, 50, 60, 75, 100, 120, 150, 200, 300, 600

The above algorithm is not optimal for this example because it performs many comparisons (starting from 540, decrementing by 1 for each iteration down to 60) to find the actual solution. So, the iteration keeps going (540, 539, 538, .........., 60) until we get 60.

There is another approach given below which is known as Euclidean algorithm. In this approach, we consider (600, 540) as a pair and divide the larger number by smaller one. This forms a new pair (540, 60) where 540 is the smaller number of previous pair and 60 is the difference between previous pair. This process repeats until one value of the pair becomes 0. This approach is faster and more efficient than the previous approach.

540 | 600 | 1
                            540
                      -----------------
                            60  | 540 | 9
                                  540
                      ------------------
                                   X
                      
                      That is, gcd(600, 540) = gcd(540, 600 mod 540)
                                             = gcd(540, 540 mod 60)
                                             = gcd(60, 0)
                                             = 60

Open in new window

Euclidean algorithm is

public int gcdEucledian(int a, int b) {
                      	while(b > 0) {
                      		int temp = a % b;
                      		a = b;
                      		b = temp;
                      	}
                      }

Open in new window

Please keep in mind that efficiency of algorithm really matters when we consider a very big number. The first approach will take forever to find the gcd of a pair that has a long long integer equal to or greater than 9,223,372,036,854,775,803. As a user would you ever use a calculator that takes 30 seconds or more to calculate gcd?

Finding GCD (Euclidean Algorithm)

Comments (0)