Steins Algorithm To Find GCD In C++

In this article, you will learn about the Stein's Algorithm to find GCD in C++ with its algorithm and examples.

What is the Stein's Algorithm?

Stein's Algorithm is an algorithm that finds the greatest common divisor of two non-negative integers, which is also known as the binary GCD algorithm . Stein's algorithm uses subtraction, comparisons, and arithmetic shifts instead of division. It is an effective way to determine two numbers' greatest common divisor (GCD).

Even though Israeli programmer and scientist Josef Stein initially published that approach in its current form in 1967 , it's possible that ancient Chinese people were aware of it as early 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 us take an example to find GCD using Stein's Algorithm in C++.

#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 us take another example to find 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:

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

Auxiliary Space:

• ✅ O(N * N), where N is the 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.