Euclidean algorithm for GCD of two numbers
The Euclidean algorithm is an efficient method for finding the GCD of two numbers. It is based on the principle that the GCD of two numbers, `a` and `b`, is the same as the GCD of `b` and the remainder of `a` divided by `b`.
For example:
int gcd_euclidean(int a, int b) {
if (b == 0)
return a;
return gcd_euclidean(b, a % b);
}
The `gcd_euclidean` function recursively calls itself with `b` as the first argument & `a % b` as the second argument until `b` becomes 0. At that point, `a` is the GCD of the original numbers.
The Euclidean algorithm has a time complexity of O(log(min(a, b))), which makes it much more efficient than the naive approach.
Optimization by checking divisibility
We can optimize the Euclidean algorithm further by checking the divisibility of the numbers before recursing. If `a` is divisible by `b`, we can directly return `b` as the GCD.
For example:
int gcd_optimized(int a, int b) {
if (b == 0)
return a;
if (a % b == 0)
return b;
return gcd_optimized(b, a % b);
}
In the `gcd_optimized` function, we first check if `b` is 0, in which case `a` is the GCD. Then, we check if `a` is divisible by `b`. If it is, we return `b` as the GCD. Otherwise, we recursively call the function with `b` & `a % b`.
Note: This optimization can save some recursive calls & improve the performance of the algorithm.
Optimization using division
We can further optimize the GCD calculation by replacing the modulo operation with division. Instead of recursively calling the function with `a % b`, we can divide `a` by `b` until `a` becomes smaller than `b` and then swap `a` and `b`.
For example:
int gcd_division(int a, int b) {
if (b == 0)
return a;
while (a >= b) {
a = a - b;
}
return gcd_division(b, a);
}
In the `gcd_division` function, we first check if `b` is 0, in which case `a` is the GCD. Then, we enter a loop where we subtract `b` from `a` until `a` becomes smaller than `b`. This step replaces the modulo operation. Finally, we recursively call the function with `b` & the updated value of `a`.
Note: This optimization can be more efficient than using the modulo operation, especially for large numbers.
Iterative implementation for GCD of two numbers using Euclidean Algorithm
While the recursive implementations of the GCD algorithms are concise & easy to understand, they might face issues with stack overflow for very large numbers. An iterative implementation can solve this problem.
For example:
int gcd_iterative(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
In the gcd_iterative function, we use a `while` loop that continues until `b` becomes 0. Inside the loop, we store the value of `b` in a temporary variable `temp`, update `b` with `a % b`, and then update `a` with the value of `temp`. This process effectively swaps `a` and `b` while updating `b` with the remainder of `a` divided by `b`.
Note: The iterative implementation has the same time complexity as the recursive Euclidean algorithm but avoids the overhead of function calls & the risk of stack overflow.
GCD of two numbers using inbuilt function
The C programming language provides a built-in function `__gcd(a, b)` in the `algorithm` library to calculate the GCD of two numbers directly.
Let’s see how to use the inbuilt function:
#include <stdio.h>
#include <algorithm>
int main() {
int a = 48, b = 60;
int gcd = __gcd(a, b);
printf("GCD of %d and %d is %d\n", a, b, gcd);
return 0;
}
You can also try this code with Online C Compiler
Output
GCD of 48 and 60 is 12
In this code, we include the `algorithm` library and directly call the `__gcd(a, b)` function with the numbers `a` and `b`. The function returns the GCD of the two numbers, which we store in the `gcd` variable and print.
Frequently Asked Questions
What is the time complexity of the Euclidean algorithm for finding the GCD?
The Euclidean algorithm has a time complexity of O(log(min(a, b))), making it efficient for large numbers.
Can the GCD algorithms be used for more than two numbers?
Yes, the GCD algorithms can be extended to find the GCD of multiple numbers by recursively finding the GCD of pairs of numbers.
Is it more efficient to use the inbuilt __gcd() function or implement the algorithm manually?
The inbuilt __gcd() function is generally more efficient and reliable, as it is optimized for performance and tested thoroughly.
Conclusion
In this article, we discussed different approaches to finding the GCD of two numbers using recursion in C. We started with the naive approach and then discussed the more efficient Euclidean algorithm. We also covered optimizations using divisibility checks and division. Moreover, we looked at the iterative implementation of the Euclidean algorithm and the use of the inbuilt __gcd() function.
You can also check out our other blogs on Code360.
7+ registered 
