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

Thumb rule for Euclid's Algorithms' efficiencies 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 numbers

Java 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;
  }
 }
}
Quick Notes explaining above code

  • 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

Recursive 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);
 }
}
Quick Notes explaining above code

  • 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

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

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.

 

Digiprove sealCopyright © 2014-2016 JavaBrahman.com, all rights reserved.