DAA: Euclid Algorithm
Euclid Algorithm
The Euclid algorithm finds the GCD of two numbers in the efficient time complexity.
To find the GCD of two numbers, we take the two numbers’ common factors and multiply them.
For example :
Let us take two numbers36 and 60, whose GCD is 12.
36 = 2 * 2 * 3 * 3 60 = 2 * 2 * 3 * 5
Basic Euclid algorithm :
The following define this algorithm
- If we subtract a smaller number from a larger (we reduce a larger number), the GCD doesn’t change. So if we keep repeatedly subtracting the larger of two, we end up with GCD.
- Instead of subtraction, if we divide the smaller number, the algorithm stops when we find remainder 0.
The approach implementation is shown below -
C++ code:
#include <bits/stdc++.h>
using namespace std;
// This function will return the GCD of a and b
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
int main()
{
int a = 10, b = 15;
cout << "GCD(" << a << ", " << b << ") = " << gcd(a, b) << endl;
a = 35, b = 10;
cout << "GCD(" << a << ", "<< b << ") = " << gcd(a, b)<< endl;
a = 31, b = 2;
cout << "GCD(" << a << ", " << b << ") = " << gcd(a, b) << endl;
return 0;
}
C code -
#include <stdio.h>
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
int main()
{
int a = 10, b = 15;
printf("GCD(%d, %d) = %dn", a, b, gcd(a, b));
a = 35, b = 10;
printf("GCD(%d, %d) = %dn", a, b, gcd(a, b));
a = 31, b = 2;
printf("GCD(%d, %d) = %dn", a, b, gcd(a, b));
return 0;
}
Java code:
import java.util.*;
import java.lang.*;
class Euclid {
public static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
public static void main(String[] args)
{
int a = 10, b = 15, g;
g = gcd(a, b);
System.out.println("GCD(" + a + " , " + b + ") = " + g);
a = 35;
b = 10;
g = gcd(a, b);
System.out.println("GCD(" + a + " , " + b + ") = " + g);
a = 31;
b = 2;
g = gcd(a, b);
System.out.println("GCD(" + a + " , " + b + ") = " + g);
}
}
Output:
GCD(10, 15) = 5 GCD(35, 10) = 5 GCD(31, 2) = 1
Time complexity: O(Log min(a, b)), where a and b are the numbers
Extended Euclid Algorithm:
The extended algorithm also finds integer coefficients x and y such that:
ax + by = gcd(a, b)
Examples:
Input: a = 30, b = 20 Output: gcd = 10 x = 1, y = -1 (Note that 30*1 + 20*(-1) = 10) Input: a = 35, b = 15 Output: gcd = 5 x = 1, y = -2 (Note that 35*1 + 15*(-2) = 5)
The extended algorithm modifies the results of our gcd using the recursive calls. Assume that x1 and y1 are the values created after recursive call of x and y. The updated x and y will be:
x = y1 - ?b/a? * x1 y = x1
C++ code:
#include <bits/stdc++.h>
using namespace std;
int gcdExtended(int a, int b, int* x, int* y)
{
// Base Case
if (a == 0) {
*x = 0;
*y = 1;
return b;
}
int x1, y1;
int gcd = gcdExtended(b % a, a, &x1, &y1);
// Update x and y using results of
// recursive call
*x = y1 - (b / a) * x1;
*y = x1;
return gcd;
}
int main()
{
int x, y, a = 35, b = 15;
int g = gcdExtended(a, b, &x, &y);
cout << "GCD(" << a << ", " << b<< ") = " << g << endl;
return 0;
}
C code:
#include <stdio.h>
int gcdExtended(int a, int b, int *x, int *y)
{
// Base Case
if (a == 0)
{
*x = 0;
*y = 1;
return b;
}
int x1, y1; // To store results of recursive call
int gcd = gcdExtended(b%a, a, &x1, &y1);
// Update x and y using results of recursive call
*x = y1 - (b/a) * x1;
*y = x1;
return gcd;
}
// Main Function
int main()
{
int x, y;
int a = 35, b = 15;
int g = gcdExtended(a, b, &x, &y);
printf("gcd(%d, %d) = %d", a, b, g);
return 0;
}
Java code:
import java.util.*;
import java.lang.*;
class Euclid
{
public static int gcdExtended(int a, int b, int x, int y)
{
// Base Case
if (a == 0)
{
x = 0; y = 1;
return b;
}
int x1=1, y1=1; // To store results of recursive call
int gcd = gcdExtended(b%a, a, x1, y1);
// Update x and y using results of recursive
// call
x = y1 - (b/a) * x1;
y = x1;
return gcd;
}
// Main function Program
public static void main(String[] args)
{
int x=1, y=1;
int a = 35, b = 15;
int g = gcdExtended(a, b, x, y);
System.out.print("gcd(" + a + " , " + b+ ") = " + g);
}
}
Output:
gcd(35, 15) = 5
How does extend Euclid works seen above, x and y are results for inputs a and b,
a.x + b.y = gcd ----(1)
And x1 and y1 are results for inputs b%a and a
(b%a).x1 + a.y1 = gcd
When we put b%a = (b - (?b/a?).a) in above,
we get following. Note that ?b/a? is floor(b/a)
(b - (?b/a?).a).x1 + a.y1 = gcd
Above equation can also be written as below
b.x1 + a.(y1 - (?b/a?).x1) = gcd ---(2)
After comparing coefficients of 'a' and 'b' in (1) and
(2), we get following
x = y1 - ?b/a? * x1
y = x1