<

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x

Finding GCD (Euclidean Algorithm)

Published on
3,999 Points
999 Views
Last Modified:
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 1234, 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?

0
Comment
0 Comments

Featured Post

JavaScript Best Practices

Save hours in development time and avoid common mistakes by learning the best practices to use for JavaScript.

Join & Write a Comment

I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
I've published three five-minute Experts Exchange video Micro Tutorials that describe terrific features in an excellent, free PDF product called PDF-XChange Editor: How to rotate pages in a PDF with free software (https://www.experts-exchange.com…

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month