Overview: This article explains Euclid’s Algorithm for Greatest Common Divisor(GCD) of 2 numbers. It then shows how to implement Euclidean Algorithm in Java with variations such as – GCD of two numbers iteratively, GCD of 2 numbers recursively and GCD of n numbers recursively.

Understanding Euclidean Algorithm for Greatest Common Divisor

Basic Version – Subtraction Based The basic algorithm given by Euclid simplifies the GCD determination process by using the principle that the greatest common divisor of two numbers does not change if the larger of the two numbers is replaced by the difference of the two. We then successively keep replacing the larger of the two numbers with their difference in multiple steps till one of the two numbers reaches zero. Lets see the algorithm with an example now.

*Example of Subtraction Based Version*: Lets find GCD of 264 and 148.

Step 0: GCD of 264 & 148

Step 1: Applying Euclid’s algorithm the numbers now become 148 & 116(264-148)

Step 2: Applying again they become 116 & 32(148-116)

Step 3: And next – 32 & 84(116-32)

Step 4: 32 & 52(84-32)

Step 5: 32 & 20(52-32)

Step 6: 20 & 12(32-20)

Step 7: 12 & 8(20-12)

Step 8: 8 & 4(12-8)

Step 9: 4 & 4(8-4)

Step 10: 4 & 0(4-4)

Since one of the numbers has reached zero, the GCD of the 264 and 148 is 4. It took us 10 steps to arrive at the GCD.

Division Based Version of Euclid’s Algorithm This version is based on the same principle of subtraction on which basic version is based but it greatly enhances the performance by using division instead of subtraction. Here, after each step the larger of the two number is replaced by the remainder obtained by dividing the larger number by the smaller number.

*Example of Division Based Version*: Lets again find GCD of 264 and 148.

Step 0: GCD of 264 & 148

Step 1: Applying division based euclidean algorithm – GCD of 116(remainder of 264/148) and 148

Step 2: Repeating same logic – GCD of 32(remainder of 148/116) and 116

Step 3: GCD of 20(remainder of 116/32) and 32

Step 4: GCD of 12(remainder of 32/20) and 20

Step 5: GCD of 8(remainder of 20/12) and 12

Step 6: GCD of 4(remainder of 12/8) and 8

Step 7: GCD of 0(remainder of 8/4) and 4

Since one of the numbers is now zero, GCD is the other number i.e. 4.

**As you can see the number of steps taken by Division based Euclidean algorithm is less than subtraction based one(7 vs 10) for the example we took. **

Going forward, **we will be writing Java code for the more efficient division based Euclidean algorithm **only in this tutorial.

Java Implementation – Iterative Method *for* Division based GCD Determination for 2 numbers

public static int gcdIterative(int bigger, int smaller) { while (true) { int remainder = bigger % smaller; if(remainder==0){ return smaller; }else{ bigger=smaller;smaller=remainder; } } }

- This is a java method which needs to be called with the first param as bigger number and second param as the smaller of the two numbers.
- It successively divides and replaces bigger number by remainder(bigger % smaller)
*iteratively*until the remainder becomes zero. It then returns the non-zero number as the GCD.

Java Implementation – Recursive Method *for* Division based GCD Determination for 2 numbers

public static int gcdRecursive(int bigger, int smaller) { int remainder = bigger % smaller; if (remainder == 0) { return smaller; } else { return gcdRecursive(smaller, remainder); } }

- This is a java method which needs to be called with the first param as bigger number and second param as the smaller of the two numbers.
- It successively divides and replaces bigger number by remainder(bigger % smaller)
*using recursion*until the remainder becomes zero. It then returns the non-zero number as the GCD.

Java Implementation – Recursive Program for Division based GCD Determination of ‘n’ numbers

public class GCDCalculator { static int[] input = { 24, 36, 72, 600 }; public static void main(String[] args) { int prevgcd = input[0]; for (int i = 1; i < input.length; i++) { if (prevgcd > input[1]) { prevgcd=gcdRecursive(prevgcd, input[i]); }else{ prevgcd=gcdRecursive(input[i],prevgcd); } } System.out.println("GCD->" + prevgcd); } public static int gcdRecursive(int bigger, int smaller) { int remainder = bigger % smaller; if (remainder == 0) { return smaller; } else { return gcdRecursive(smaller, remainder); } } }

**OUTPUT of the above code**

Quick Notes explaining the above program

- Java program which calculates GCD of 4 numbers. Will work for any amount of numbers, just add more numbers in the
`static int[] input`

variable when it is initialized. - The
`main()`

method determines GCD of numbers 2 at a time using the recursive GCD method we defined earlier. Once the GCD of first 2 numbers is obtained then it calls for GCD of third number with GCD of first 2 numbers, and so on. This works because GCD of two numbers can be effectively used instead of the 2 numbers themselves.

Summary

This article explained the Euclidean algorithm for GCD determination starting with the subtraction based Euclidean Algorithm and then explained the more efficient division based version of the algorithm. Next it gave Java methods for division based algorithm both iteratively and recursively for 2 numbers. Lastly, it showed a complete Java program for division based Euclidean algorithm for GCD determination for n numbers.

Copyright © 2014-2017 JavaBrahman.com, all rights reserved.