Steins Algorithm To Find GCD In C++

In this guide, you will explore Stein's Algorithm for calculating the Greatest Common Divisor (GCD) in C++ along with its implementation and illustrative instances.

What is the Stein's Algorithm?

Stein's Algorithm is a method used to determine the highest common factor of two non-negative integers, commonly referred to as the binary GCD algorithm. This technique relies on subtraction, comparisons, and arithmetic shifts rather than division. It proves to be a efficient approach for calculating the greatest common divisor (GCD) of two numbers.

While the current version of this method was first documented by Israeli programmer and scientist Josef Stein in 1967, there is a possibility that individuals in ancient China may have had knowledge of it as far back as the second century BCE.

Examples:

Input:

a = 24 b = 30

Output:

Input:

a = 36, b = 60

Output:

Algorithm:

The algorithm finds the GCD of two nonnegative numbers x and y by repeatedly applying these identities:

• ✅ gcd(x,0) = x: everything divides zero, and y is the largest number that divides
• ✅ gcd(2x,2y) = 2 . gcd(x,y): Here, 2 a common divisor.
• ✅ gcd(x,2y)=gcd(x,y): if x is odd, 2 is not a common divisor.
• ✅ gcd(x,y) = gcd(x, y-x): if x, y odd and x<=y.
• ✅ As GCD is commutative ((gcd(x,y = gcd(y,x)), those identities still apply if the operands are swapped: gcd(0,y) = y, gcd(2x,y) = gcd(x,y) if y is odd, etc.

Stein's approach to find the GCD of two numbers, gcd (a, b):-

• ✅ GCD is zero if a and b are both 0. gcd(0, 0) = 0.
• ✅ Since everything divides zero, gcd(a, 0) = a and gcd(0, b) = b.
• ✅ Given that 2 is a common divisor, gcd(a, b) = 2*gcd(a/2, b/2) if a and b are both even.
• ✅ The bitwise shift operator can be used to perform multiplication by two.
• ✅ You have gcd(a, b) = gcd(a/2, b) if a is even and b is odd. Similarly, gcd(a, b) = gcd(a, b/2) if a is odd and b is even. It's because 2 can never be divided by two.
• ✅ When a and b are both odd, the formula for gcd(a, b) is gcd(|a-b|/2, b) . When two odd numbers vary, the difference is even. Continue steps 3-5 until either a = b or a = 0. In either scenario, the GCD equals power(2, k) * b, where k is the number of common factors of 2 identified in step 3 and power(2, k) is 2 raised to the power of k.

Example 1:

Let's consider an example to calculate the Greatest Common Divisor (GCD) using Stein's Algorithm in the C++ programming language.

#include <bits/stdc++.h>
using namespace std;
// Function to implement
// Stein's Algorithm
int gcd(int a, int b)
{
	/* GCD(0, b) == b; GCD(a, 0) == a,
	GCD(0, 0) == 0 */
	if (a == 0)
		return b;
	if (b == 0)
		return a;
	/*Finding K, where K is the
	the greatest power of 2
	that divides both a and b. */
	int k;
	for (k = 0; ((a | b) & 1) == 0; ++k) 
	{
		a >>= 1;
		b >>= 1;
	}
	/* Dividing a by 2 until a becomes odd */
	while ((a & 1) == 0)
		a >>= 1;
	/* From here on, 'a' is always odd. */
	do
	{
		/* If b is even, remove all factors of 2 in b */
		while ((b & 1) == 0)
			b >>= 1;
		/* Now a and b are both odd.
		Swap if necessary so a <= b,
		then set b = b - a (which is even).*/
		if (a > b)
			swap(a, b); // Swap u and v.
		b = (b - a);
	}while (b != 0);
	/* restore common factors of 2 */
	return a << k;
}
// Driver code
int main()
{
	int a = 34, b = 17;
	printf("Gcd of given numbers is %d\n", gcd(a, b));
	return 0;
}

Output:

Complexity Analysis:

Time Complexity:

• ✅ O(N * N)

Auxiliary Space:

Example 2:

Let's consider another instance to determine the Greatest Common Divisor (GCD) using Stein's Algorithm:

// Recursive C++ program to implement Stein's Algorithm
#include <bits/stdc++.h>
using namespace std;
// Function to implement
// Stein's Algorithm
int gcd(int a, int b)
{
	if (a == b)
		return a;
	// GCD(0, b) == b; GCD(a, 0) == a,
	// GCD(0, 0) == 0
	if (a == 0)
		return b;
	if (b == 0)
		return a;
	// look for factors of 2
	if (~a & 1) // a is even
	{
		if (b & 1) // b is odd
			return gcd(a >> 1, b);
		else // both a and b are even
			return gcd(a >> 1, b >> 1) << 1;
}
	if (~b & 1) // a is odd, b is even
		return gcd(a, b >> 1);
	// reduce larger number
	if (a > b)
		return gcd((a - b) >> 1, b);
	return gcd((b - a) >> 1, a);
}
// Driver code
int main()
{
	int a = 34, b = 17;
	printf("Gcd of given numbers is %d\n", gcd(a, b));
	return 0;
}

Output:

Complexity Analysis:

Time Complexity:

The time complexity is

• ✅ O(N * N), where N represents the total number of bits present in the larger number.

Auxiliary Space:

Requires O(N * N) space, where N represents the total number of bits in the larger number.

Benefits of Stein's Algorithm over Euclid's Algorithm to find GCD of two numbers:

• ✅ Stein's Algorithm is the optimized version of Euclid's Algorithm.
• ✅ It is more effective because it uses a bitwise shift operator.