Binary Greatest Common Divisor Finder Algorithm
The Binary Greatest Common Divisor (GCD) Finder Algorithm, also known as the Binary Euclidean Algorithm or Stein's Algorithm, is an efficient method for computing the greatest common divisor of two non-negative integers. The greatest common divisor is the largest positive integer that divides both numbers without leaving a remainder. The binary GCD algorithm is based on the principle of reducing the problem of finding the GCD of two numbers to the problem of finding the GCD of two smaller numbers. It does so by exploiting the properties of even and odd numbers and bitwise operations, making it faster than the traditional Euclidean Algorithm in certain cases, especially in modern computer systems where bitwise operations are highly optimized.
The algorithm follows a series of steps to repeatedly reduce the given numbers until they reach a common divisor. First, it checks if either of the numbers is zero, in which case the GCD is the non-zero number. If both numbers are even, their GCD must be even, so it divides both numbers by 2 and multiplies the result by 2 at the end. If one of the numbers is even, it is divided by 2 to reduce its size. If both numbers are odd, their difference is calculated and halved if even. The process is repeated until both numbers become equal, which is the GCD. The binary GCD algorithm is advantageous in terms of computational efficiency since bitwise operations are faster than arithmetic operations like division and modulo. The algorithm is particularly well-suited for large integers and computer systems where bitwise operations are highly efficient.
using System;
namespace Algorithms.Numeric.GreatestCommonDivisor
{
/// <summary>
/// TODO.
/// </summary>
public class BinaryGreatestCommonDivisorFinder : IGreatestCommonDivisorFinder
{
/// <summary>
/// Finds greatest common divisor for numbers u and v
/// using binary algorithm.
/// Wiki: https://en.wikipedia.org/wiki/Binary_GCD_algorithm.
/// </summary>
/// <param name="u">TODO.</param>
/// <param name="v">TODO. 2.</param>
/// <returns>Greatest common divisor.</returns>
public int Find(int u, int v)
{
// GCD(0, 0) = 0
if (u == 0 && v == 0)
{
return int.MaxValue;
}
// GCD(0, v) = v; GCD(u, 0) = u
if (u == 0 || v == 0)
{
return u + v;
}
// GCD(-a, -b) = GCD(-a, b) = GCD(a, -b) = GCD(a, b)
u = Math.Sign(u) * u;
v = Math.Sign(v) * v;
// Let shift := lg K, where K is the greatest power of 2 dividing both u and v
var shift = 0;
while (((u | v) & 1) == 0)
{
u >>= 1;
v >>= 1;
shift++;
}
while ((u & 1) == 0)
{
u >>= 1;
}
// From here on, u is always odd
do
{
// Remove all factors of 2 in v as they are not common
// v is not zero, so while will terminate
while ((v & 1) == 0)
{
v >>= 1;
}
// Now u and v are both odd. Swap if necessary so u <= v,
if (u > v)
{
var t = v;
v = u;
u = t;
}
// Here v >= u and v - u is even
v -= u;
}
while (v != 0);
// Restore common factors of 2
return u << shift;
}
}
}
