.NET 1.1+

Stein's Algorithm (2)

Stein's algorithm provides an enhanced version of the Euclidean algorithm for calculating the greatest common divisor (GCD) for a pair of integers. Stein's algorithm provides greater efficiency by making use of the bitwise shift operators.

Creating the Stein Method

Let's create a method that implement's Stein's algorithm. Start by creating the signature, which matches that of the earlier Euclid method.

public static uint Stein(uint value1, uint value2)
{
}

To implement rules 1 and 2, we need to check if either of the two values are zero or if they match. These scenarios cause a value to be returned without further recursive calls to the method.

if (value1 == 0) return value2;
if (value2 == 0) return value1;
if (value1 == value2) return value1;

Finally we can determine which of the values are odd and which are even, in order that we can apply the remaining rules with a recursive call. The first if statement identifies when both values are even and applies rule 3. The second and third if statements capture one even and one odd number, both applying rule 4. The last if statement and the final else statement are executed when both values are odd. They both apply rule 5.

bool value1IsEven = (value1 & 1u) == 0;
bool value2IsEven = (value2 & 1u) == 0;

if (value1IsEven && value2IsEven)
    return Stein(value1 >> 1, value2 >> 1) << 1;
else if (value1IsEven && !value2IsEven)
    return Stein(value1 >> 1, value2);
else if (value2IsEven)
    return Stein(value1, value2 >> 1);
else if (value1 > value2)
    return Stein((value1 - value2) >> 1, value2);
else
    return Stein(value1, (value2 - value1) >> 1);

Testing the Method

To perform a simple test, add the following line of code to the Main method and run the program. This calculates the GCD of 116,150 and 232,704. The result should be 202.

int gcd = Stein(116150, 232704); // 202