Euclidean Algorithm for Greatest Common Divisor (GCD) in Java

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.

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.

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.

Going forward,

Java Implementation - Iterative Method
Quick Notes explaining above code

Java Implementation - Recursive Method
Quick Notes explaining above code

Quick Notes explaining the above program

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*: Let us 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.

*Example of Division Based Version*: Let us 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.**
Thumb rule for Euclid's Algorithms' efficiencies

Division based algorithm gives the
GCD of 2 numbers in number of steps less than or equal to 5 times the number of digits in the smaller number for
base 10 numbers.

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 numbersJava 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.

*for*Division based GCD Determination for 2 numbersRecursive Java 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.

Recursive Java 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**GCD -> 12

- 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.