1. Overview
In mathematics, the GCD of two integers, which are non-zero, is the largest positive integer that divides each of the integers evenly.
In this tutorial, we’ll look at three approaches to find the Greatest Common Divisor (GCD) of two integers. Further, we’ll look at their implementation in Java.
2. Brute Force
For our first approach, we iterate from 1 to the smallest number given and check whether the given integers are divisible by the index. The largest index which divides the given numbers is the GCD of the given numbers:
int gcdByBruteForce(int n1, int n2) {
int gcd = 1;
for (int i = 1; i <= n1 && i <= n2; i++) {
if (n1 % i == 0 && n2 % i == 0) {
gcd = i;
}
}
return gcd;
}
As we can see, the complexity of the above implementation is O(min(n1, n2)) because we need to iterate over the loop for n times (equivalent to the smaller number) to find the GCD.
3. Euclid’s Algorithm
Second, we can use Euclid’s algorithm to find the GCD. Euclid’s algorithm is not only efficient but also easy to understand and easy to implement using recursion in Java.
Euclid’s method depends on two important theorems:
- First, if we subtract the smaller number from the larger number, the GCD doesn’t change – therefore, if we keep on subtracting the number we finally end up with their GCD
- Second, when the smaller number exactly divides the larger number, the smaller number is the GCD of the two given numbers.
Note in our implementation that we’ll use modulo instead of subtraction since it’s basically many subtractions at a time:
int gcdByEuclidsAlgorithm(int n1, int n2) {
if (n2 == 0) {
return n1;
}
return gcdByEuclidsAlgorithm(n2, n1 % n2);
}
Also, note how we use n2 in n1‘s position and use the remainder in n2’s position in the recursive step of the algorithm.
Further, the complexity of Euclid’s algorithm is O(Log min(n1, n2)) which is better as compared to the Brute Force method we saw before.
4. Stein’s Algorithm or Binary GCD Algorithm
Finally, we can use Stein’s algorithm, also known as the Binary GCD algorithm, to find the GCD of two non-negative integers. This algorithm uses simple arithmetic operations like arithmetic shifts, comparison, and subtraction.
Stein’s algorithm repeatedly applies the following basic identities related to GCDs to find GCD of two non-negative integers:
- gcd(0, 0) = 0, gcd(n1, 0) = n1, gcd(0, n2) = n2
- When n1 and n2 are both even integers, then gcd(n1, n2) = 2 * gcd(n1/2, n2/2), since 2 is the common divisor
- If n1 is even integer and n2 is odd integer, then gcd(n1, n2) = gcd(n1/2, n2), since 2 is not the common divisor and vice versa
- If n1 and n2 are both odd integers, and n1 >= n2, then gcd(n1, n2) = gcd((n1-n2)/2, n2) and vice versa
We repeat steps 2-4 until n1 equals n2, or n1 = 0. The GCD is (2n) * n2. Here, n is the number of times 2 is found common in n1 and n2 while performing step 2:
int gcdBySteinsAlgorithm(int n1, int n2) {
if (n1 == 0) {
return n2;
}
if (n2 == 0) {
return n1;
}
int n;
for (n = 0; ((n1 | n2) & 1) == 0; n++) {
n1 >>= 1;
n2 >>= 1;
}
while ((n1 & 1) == 0) {
n1 >>= 1;
}
do {
while ((n2 & 1) == 0) {
n2 >>= 1;
}
if (n1 > n2) {
int temp = n1;
n1 = n2;
n2 = temp;
}
n2 = (n2 - n1);
} while (n2 != 0);
return n1 << n;
}
We can see that we use arithmetic shift operations in order to divide or multiply by 2. Further, we use subtraction in order to reduce the given numbers.
The complexity of Stein’s algorithm when n1 > n2 is O((log2n1)2) whereas. when n1 < n2, it is O((log2n2)2).
5. Conclusion
In this tutorial, we looked at various methods for calculating the GCD of two numbers. We also implemented these in Java and had a quick look at their complexity.
As always, the full source code of our examples here is, as always, over on GitHub.
