Euclidean Algorithm for GCD: Repeated Subtraction
The Euclidean algorithm is a more efficient method for finding the greatest common divisor (GCD) of two numbers compared to the general method. This algorithm is based on the principle that the GCD of two numbers also divides their difference. The method using repeated subtraction repeatedly subtracts the smaller number from the larger one until the two numbers become equal. This equal number at the end is the GCD.
To understand this better, let's go through the process with an example using the numbers 48 and 18:
-
Subtract the smaller number (18) from the larger number (48) to get a new pair of numbers: 30 and 18.
-
Repeat the process: subtract 18 from 30 to get 12 and 18.
-
Continue subtracting the smaller from the larger: now subtract 12 from 18 to get 6 and 12.
-
Subtract 6 from 12 to get 6 and 6.
-
The numbers are now the same, and we cannot subtract further. Both numbers are 6, which is the GCD.
Here's how you can implement this using Java:
Java
public class EuclideanSubtraction {
public static int gcdBySubtraction(int a, int b) {
while (a != b) {
if (a > b) {
a -= b; // subtract b from a
} else {
b -= a; // subtract a from b
}
}
return a; // or b, since a and b are equal here
}
public static void main(String[] args) {
int num1 = 48, num2 = 18;
System.out.println("The GCD of " + num1 + " & " + num2 + " is " + gcdBySubtraction(num1, num2));
}
}
You can also try this code with Online Java Compiler
Output
The GCD of 48 & 18 is 6
In this Java program, we use a while loop to perform the subtraction repeatedly until the two numbers are equal. This condition (while (a != b)) keeps the loop running until we find the GCD. The method is more efficient than checking every possible divisor because it reduces the problem size more quickly.
Note -: This approach is particularly effective for numbers that are not too far apart in size or when one number is not much larger than the other.
Euclidean Algorithm for GCD: Repeated Division
The repeated division version of the Euclidean algorithm is an optimization over the subtraction method and is generally faster, especially for larger numbers. This method reduces the larger number by finding the remainder when the larger number is divided by the smaller one. This process repeats until the remainder is zero. The non-zero remainder just before the zero remainder is the greatest common divisor (GCD).
Here’s how it works step-by-step, using the same example numbers, 48 and 18:
-
Divide the larger number (48) by the smaller number (18) and take the remainder: 48 divided by 18 is 2 with a remainder of 12.
-
Now, use 18 as the larger number and 12 as the smaller number and repeat: 18 divided by 12 is 1 with a remainder of 6.
-
Continue with 12 and 6: 12 divided by 6 is 2 with a remainder of 0.
-
Since the remainder is now 0, the last non-zero remainder (6) is the GCD.
The Java implementation of this method is shown below:
Java
public class EuclideanDivision {
public static int gcdByDivision(int a, int b) {
while (b != 0) {
int temp = b; // temporarily store the value of b
b = a % b; // replace b with the remainder of a divided by b
a = temp; // replace a with the old value of b
}
return a; // when b is 0, a is the GCD
}
public static void main(String[] args) {
int num1 = 48, num2 = 18;
System.out.println("The GCD of " + num1 + " & " + num2 + " is " + gcdByDivision(num1, num2));
}
}
You can also try this code with Online Java Compiler
Output
The GCD of 48 & 18 is 6
In this program, we use a while loop that runs until the second number (b) becomes zero. The key operation inside the loop is the modulus operation (a % b), which gives the remainder when a is divided by b. Each iteration updates a and b to the previous values of b and the remainder, respectively. This method efficiently narrows down the possible values for the GCD by using division, which typically reduces the problem size more significantly with each step compared to subtraction.
Note -: This variation of the Euclidean algorithm is widely used due to its efficiency and simplicity. It’s particularly useful in programming and computational applications where minimizing computation time is crucial.
Frequently Asked Questions
Why is the Euclidean algorithm considered efficient for finding GCD?
The Euclidean algorithm reduces the problem size significantly with each step, whether by subtraction or division, allowing it to quickly find the GCD even for large numbers. This efficiency is crucial in computational mathematics and programming.
Can the Euclidean algorithm be used for more than two numbers?
Yes, to find the GCD of more than two numbers, you can apply the Euclidean algorithm iteratively. Start with two numbers, find their GCD, and then use that GCD with the next number. Repeat this process until all numbers are included.
What happens if one of the numbers in the GCD calculation is zero?
If one of the numbers is zero and the other is a non-zero integer, the GCD is the non-zero number. This is because any number divided by zero is undefined, but every number is a divisor of zero.
Conclusion
In this article, we have learned about the greatest common divisor (GCD) and its importance in mathematical computations and programming. We started with a general method of finding the GCD through exhaustive divisor checks, then moved to more efficient techniques using the Euclidean algorithm, first with repeated subtraction and then with repeated division. Each method was illustrated with Java code examples, demonstrating their practical implementation.
You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.
85+ registered