Number Theory - Greatest Common Divisor (G.C.D) Algorithms
Hope, you are enjoying this series of articles on number theory and
learning from it efficiently.
So, we are back with our brand-new article on GCD algorithms, be relaxed and keep reading, we will make sure that after reading this article you will understand what is GCD and will be able to code an efficient solution for finding GCD of two numbers 😊
1. What is Greatest Common Divisor (GCD) ?
Greatest Common Divisor (G.C.D) or Highest Common Factor ( H.C.F) of two numbers is defined as the largest number
that divides both numbers.
For instance, the GCD of 12 and 16 is 4, because 4 divides both 12 and 16 and no other number greater than 4 shows this property.
Here is how we calculated GCD, Factors of 12 = 2 x 2 x 3
Factors of 16 = 2 x 2 x 2 x 2
Now, We will find how many common factors exist for both of them: 2 x 2 = 4 Hence GCD of 12 and 16 is 4.
2. Naïve Approach – Brute Force:
As you may have predicted this is a brute force approach so we will be checking for every possible case.
Basically, we will be doing same process as explained above i.e. we will start checking from minimum of two numbers and iterate till 1, and in each iteration we will be checking that if given two numbers are divisible by it or not, if it is divisible we have got our GCD (we will stop iteration and return it) else we will continue the same process.
Note: The GCD of two numbers (let’s say a and b) lie in between
minimum(a,b) to 1.
E.g. GCD(12,16) will lie in between minimum(12,16) = 12 and 1 i.e. GCD(12,16) = 4.
Below is the implementation of naïve approach:
Time Complexity = O( min(a,b) )
2. Euclid’s Algorithm – O( log(min(a,b)) ):
As learned from previous article if you want to optimize any approach try
to figure out some observations from it.
Observation: The Euclidean algorithm is based on the following key observation: if d divides a and d divides b, then d also divides
a − b.
Note: Same goes for Addition also i.e if d divides a and d divides b, then d also divides a + b.
E.g. 4 divides 12 and 4 divides 20,and hence 4 also divides (20 - 12) i.e. 8.
This means that the GCD of a and b is the same as the GCD of a−b and b, which is progress since this makes the numbers smaller.
As a result, we can repeat this process to form an optimized algorithm:
If a = b, stop -- the GCD of a and a is, of course, a. Otherwise, go to
If a > b, replace a with a − b, and go back to step 1.
- If b > a, replace b with b − a, and go back to step 1.
Determine the greatest common factor of 84 and 132.
We follow our algorithm:
1. a is 84 and b is 132. Since b > a, we replace b with b – a = 132 – 84 = 48.
2. a is 84 and b is 48. Since a > b, we replace a with a – b = 84 – 48 = 36
3. a is 36 and b is 48. Since b > a, we replace b with b – a = 12
4. a is 36 and b is 12. Since a > b, we replace a with a – b = 24
5. a is 24 and b is 12. Since a > b, we replace a with a – b = 12
6. a is 12 and b is 12. Since a = b, the GCD is 12.
Below is the implementation of optimized approach:
Time Complexity: O( left to you, try it out… it would be fun !! )
In this particular approach as discussed above we can furthermore optimize
it with using modular operation rather than subtracting two numbers.
Now instead of subtraction, if we divide smaller number, the algorithm stops when we find remainder 0.
formally defined as below:
GCD(a,b) = a if b = 0
GCD(b, a % b) otherwise
let’s take an example to understand it more clearly, Consider GCD of 12 and 140, we will proceed as follows. Here, a = 12, b = 140
GCD(12 , 140 ) à GCD(140, 12 % 140 ) à GCD(140 , 12 ) à GCD(12 , 140 % 12 )
à GCD(12 , 8 ) à GCD(8 , 12 % 8 ) à GCD(8 , 4 ) à GCD(4 , 8 % 4 ) à GCD(4,0)
Hence, finally we got b = 0 therefore our GCD came out to be 4.
Below is the implementation of above approach:
Time Complexity: O( log( min(a,b) ) )
There is one more algorithm which is to be considered while learning GCD
named Extended Euclid’s Algorithm.
It is basically a extension of above algorithm as it wont optimize Euclid Algorithm more but it is useful for calculating Modulo Multiplicative Inverse.
But we will not be learning Extended Euclid’s Algorithm in this article as it has some concepts of modulo multiplicative inverse so we will first get ourselves familiar with modular arithmetic and then we will understand this algorithm as we don’t believe in giving half knowledge to our readers 😊
It is always better to solve a question after you learn a new concept as it helps in making concrete concepts.
So, below are problems which are handpicked by Programmers Army to make your concept more solid which you learned.
1. Problem from CodeChef:
2. Problem from SPOJ: https://www.spoj.com/problems /SUMGCD/
We highly recommend to solve above problems if you got stuck read editorials for guidance.
So that’s it for this article we will be coming up with our next article on further topics of number theory very soon till then keep learning, keep coding, keep reading and keep improving !!
Happy Coding 😊
By Programmers Army