.NET 1.1+

Stein's Algorithm

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.

Greatest Common Divisor

In an earlier article I showed a C# version of the Euclidean algorithm, described by the Greek mathematician, Euclid of Alexandria. This algorithm can be used to calculate the greatest common divisor (GCD) of two integers. The GCD is the largest whole number that both integers can be divided by without generating a remainder. For example, the GCD of 210 and 124 is 42, as both values can be divided by 42 without remainder, giving results of 5 and 3 respectively.

The most basic version of the Euclidean algorithm works by repeated subtraction. I won't describe it here as it is covered in the earlier article. It can be incorporated into a C# method as follows:

public static uint Euclid(uint value1, uint value2)
{
    while (value1 != 0 && value2 != 0)
    {
        if (value1 > value2)
            value1 -= value2;
        else
            value2 -= value1;
    }
    return Math.Max(value1, value2);
}

NB: The method is shown as static so that it can be called directly from the Main method of a console application project.

Stein's Algorithm

Stein's algorithm, published in 1967 by Josef Stein, is another algorithm for calculating the GCD of two values. It is optimised for use in computing, utilising fast bitwise shifts rather than the usually slower repeated subtraction, division or modulus operations. Computers that use the .NET framework generally have processors that natively support division so the efficiency difference may not be so pronounced. However, the algorithm is still interesting.

Stein's algorithm uses a number of rules:

1. Like the Euclidean algorithm, if either of the two values is zero, the result of the algorithm is the other value. This can be returned immediately.
2. If the two integer values are equal, the GCD is this value and can be returned immediately.
3. If both of the values are even numbers we know that the value two is a common divisor. We can divide both values by two, using a shift operation, and find the GCD of the two new values. Multiplying this result by two, using a second shift operation, gives the GCD of the original values. ie. GCD(a,b) = 2·GCD(a/2,b/2).
4. If only one of the values is even, we know that the value two is not a common divisor. We can therefore divide the even value by two and recalculate the GCD. ie. GCD(even,odd) = GCD(even/2,odd).
5. If both of the values are odd, we need to use subtraction in the same manner as in a single step of the Euclidean algorithm. The smaller value is subtracted from the larger and the result is used with the smaller value to calculate the GCD. ie. GCD(large,small) = GCD(large-small,small). We can go a step further than this. When one odd value is subtracted from another we know that the result will be even. This means that we will be calculating the GCD of an odd and an even value. We can therefore divide the even number by two, as in step 4. ie. GCD(large,small) = GCD((large-small)/2,small).