Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Euclidean Algorithm
2.1.
Algorithm 
2.2.
Code 
2.3.
Output 
2.4.
Example 
3.
Extended Euclidean Algorithm 
3.1.
Algorithm 
3.2.
Code 
3.3.
Output 
4.
Frequently Asked Questions
4.1.
Why Euclid's algorithm is used?
4.2.
What would be the GCD of 12 and 4 if 4 were the GCD of 16 and 12?
4.3.
How many steps does Euclid's algorithm have to take to solve a problem, according to Gabriel Lame?
4.4.
How long does the binary GCD algorithm run overall?
4.5.
How long does Euclid's algorithm take to run in its entirety?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

What is the Euclidean Algorithm?

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

The Euclidean algorithm, also known as Euclid's algorithm, is an effective way to determine the greatest common divisor (GCD), or the biggest number that divides two integers (numbers) evenly without leaving a remainder. The Greek mathematician Euclid, who first described it in his Elements, gave it his name.

Introduction image

In this article, we will discuss the euclidean algorithm in detail. So, Stay till the end!

Euclidean Algorithm

The Euclidean algorithm is based on the premise that if the larger number is swapped out for its difference with the smaller number, the greatest common divisor of the two numbers remains the same. For instance, the GCD of 252 and 105 is 21 (because 252 = 21 x 12 and 105 = 21x5), and 21 is also the GCD of 105 and 252-105 = 147. Repeating this method results in gradually smaller pairs of numbers until the two numbers are equal since this replacement reduce the larger of the two numbers. They are the GCD of the initial two numbers when that happens. The GCD can be written as the linear combination of the two original numbers, that is, the sum of the two integers, each multiplied by an integer (for instance, 21 = 5x105 + (-2) x 252), by reversing the steps or applying the extended Euclidean method. 

Algorithm 

  • GCD remains the same if we lower a larger integer by subtracting a smaller one. Therefore, if we repeatedly deduct the larger of two, we arrive at GCD.
  • Now, if we divide the smaller number rather of subtracting it, the process halts when we reach the final result of 0.

Code 

#include <bits/stdc++.h>
using namespace std;
int gcd(int p, int q)
{
    if (p == 0)
        return q;
    return gcd(q % p, p);
}
int main()
{
    int p = 256, q = 12;
    // Function call
    cout << "GCD(" << p << "," << q << "`) = " << gcd(p, q) << endl;
    p = 42, q = 7;
    cout << "GCD(" << p << "," << q << ") = " << gcd(p, q) << endl;
    p = 35, q = 7;
    cout << "GCD(" << p << "," << q << ") = " << gcd(p, q) << endl;
    return 0;
}

Output 

output

Time Complexity: O(Log min(p, q))

Auxiliary Space: O(Log (min(p, q))

Example 

  1. Find the GCD of 192 and 78
  • A=192, B=78
  • A ≠0
  • B ≠0
  • Use long division to find that 192/78 = 2 with a remainder of 36. We can write this as:
  • 192 = 78 * 2 + 36

2. Find GCD(78,36), since GCD(192,78)=GCD(78,36)

  • A=78, B=36
  • A ≠0
  • B ≠0
  • Use long division to find that 78/36 = 2 with a remainder of 6. We can write this as:
  • 78 = 36 * 2 + 6

3. Find GCD(36,6), since GCD(78,36)=GCD(36,6)

  • A=36, B=6
  • A ≠0
  • B ≠0
  • Use long division to find that 36/6 = 6 with a remainder of 0. We can write this as:
  • 36 = 6 * 6 + 0

4. Find GCD(6,0), since GCD(36,6)=GCD(6,0)

  • A=6, B=0
  • A ≠0
  • B =0, GCD(6,0)=6

So we have shown:

GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6

GCD(192,78) = 6

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Extended Euclidean Algorithm 

The Euclidean algorithm merely determines the greatest common divisor (GCD) of two numbers p and q; however, the extended version additionally discovers a way to describe GCD in terms of p and q, i.e., coefficients x and y, for which 

p.x + q.y = gcd(p, q)


It's crucial to remember that we can always find a representation of this gcd(55, 80) = 5. Therefore we can represent five as a linear combination with terms 55 and 80: 55.3 + 80.(-2) = 5

Algorithm 

In this part, we will use the symbol g to indicate the GCD of p and q.
 

  • The original algorithm has only undergone minor modifications. Considering the method, we can see that p = g and b = 0 signify the program's conclusion. We can quickly discover coefficients for these parameters, namely g .1 + 0.0 = g.
     
  • Starting from these coefficients  (a, b) = (1, 0), we can back up the recursive calls. We need to figure out how the coefficients a  and b  change during the transition from  (p, q)  to  (q, p mod q).
     
  • Let us assume we found the coefficients  (a1, b1)  for  (q, p mod q) : q.a1 + (p mod p).b1 = g and, 
     
  • we want to find the pair  (a, b)  for  (p, q) : p.a + q.b = g
     
  • We can represent a mod b as: p mod q = p - floor(p/q).q, Substituting this expression in the coefficient equation of  (a1, b1)  gives:  g = q.a1 + (p mod q).b1 = q.a1 + (p - floor(p/q).q).b1. 
     
  • Rearranging the terms  g = p.b1 + q.(a1 - b1.floor(p/q)) 
     
  • We found the values a and b: a = b1 and b = a1 - b1.floor(p/q) 

Code 

#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b, int &x, int &y)
{
    a = 1, b= 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1)
    {
        int q = a1 / b1;
        tie(a, x1) = make_tuple(x1, a - q * x1);
        tie(b, y1) = make_tuple(y1, b - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}
int main()
{
    int p = 256, q = 12;
    int a, b;
    // Function call
    cout << "GCD(" << p << "," << q << ") = " << gcd(p, q, a, b) << endl;
    p = 25, q = 5;
    cout << "GCD(" << p << "," << q << ") = " << gcd(p, q, a, b) << endl;
    p = 35, q = 7;
    cout << "GCD(" << p << "," << q << ") = " << gcd(p, q, a, b) << endl;
    return 0;
}

Output 

output

Time Complexity: O(Log min(p, q))

Auxiliary Space: O(Log (min(p, q))

Frequently Asked Questions

Why Euclid's algorithm is used?

The GCD of two numbers may generally be found using Euclid's approach. Three or more integers cannot be applied simultaneously in a direct manner. 

What would be the GCD of 12 and 4 if 4 were the GCD of 16 and 12?

According to Euclid's algorithm, even if a difference of two numbers changes the larger number, the GCD of the two numbers remains unchanged. GCD of 16 and 12 and 12 and (16-12)=4, therefore, equals 4.

How many steps does Euclid's algorithm have to take to solve a problem, according to Gabriel Lame?

The number of digits needed by Euclid's algorithm is fewer than five times that amount. The algorithm divides two numbers. When a remainder of zero is reached, it ends.

How long does the binary GCD algorithm run overall?

The binary GCD algorithm is the sub-division of the Euclidean algorithm with faster operations. Its running time is given by O(N^2).

How long does Euclid's algorithm take to run in its entirety?

According to Lame's research, Euclid's algorithm's total running time is O (N). 

Conclusion

In this article, we discussed the euclidean algorithm in detail, along with some examples for a good understanding of the Euclidean algorithm. 
Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available; look at the Top 150 Interview Puzzles interview experiences, and interview bundle for placement preparations. Read our blogs on aptitudecompetitive programminginterview questionsIT certifications, and data structures and algorithms for the best practice.

Previous article
Introduction to Public Key Cryptography
Next article
What is the Chinese Remainder theorem?
Live masterclass