.NET 1.1+

Euclid's Algorithm

by Richard Carr, published at http://www.blackwasp.co.uk/EuclidsAlgorithm.aspx

Euclid's algorithm, also known as the Euclidean algorithm, can be used to efficiently calculate the greatest common divisor (GCD) for two integer values. This article describes the algorithm and provides several C# methods that calculate the GCD.

Greatest Common Divisor

Euclid's algorithm, which is often called the Euclidean algorithm, is an algorithm described by the Greek mathematician, Euclid of Alexandria. The algorithm seeks to calculate the greatest common divisor (GCD) of two arbitrarily large integers; the GCD being the largest whole number that can the two values can be divided by without remainder. The algorithm uses the fact that when two numbers share a common divisor, subtracting the smaller number from the larger yields a result that also shares the common divisor.

As an example, let's consider the values 210 and 126. The GCD of these two numbers is 42. Note that 210 / 42 = 5 and 126 / 4 = 3. If we were to subtract the smaller value from the larger we get 210 - 126 = 84. This too divides equally by 42, giving the result, 2.

If the process of subtracting the smaller number from the larger is repeated, eventually one of the values will become zero. At this point, the other value will contain the GCD for the original pair. This iterative process for our example values yields the following results:

210 - 126 = 84
126 - 84 = 42
84 - 42 = 42
42 - 42 = 0

The final calculation gives a zero result, which would leave the two values 42 and zero. Therefore, the GCD is the value 42.

Implementing Euclid's Algorithm

For the first implementation of the algorithm we will follow the steps described above directly. We will create a static method that has two integer parameters and returns a third integer containing the GCD. The method is static so that it can be called easily from the Main method of a console application without instantiating objects. You may decide to implement it as an instance method for your own project.

The method has several steps. Initially a while loop is created that will continue processing until one of the values has been reduced to zero. Within the loop the smaller of the two values is subtracted from the larger. Once the loop has exited, one value will be zero and the other will contain the GCD. The GCD is returned by finding the larger of the two values. NB: The code in this article assumes that both integers are positive.

To create the method, add the following code:

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

To test the method, try executing the following command. This finds the GCD of 116,150 and 232,704. The result should be 202.

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

Obtaining the GCD Using the Modulus Operator

The number of iterations of the loop in the previous code sample can be excessive. If one of the two values is much larger than the other, either at the beginning of the process or later as the values fall, the same value may be subtracted many times. We can reduce the number of iterations using the modulus operator. Applying the modulus operator to the two values and exchanging the larger value for the result has the effect of applying multiple subtractions simultaneously. For example, if the two values were ten and three, the three would be subtracted three times to reduce the ten to one. Using the modulus we get the one in a single iteration, as 10 % 3 = 1. If the result of the modulus is zero, the GCD has been found.

public static int GetGCDByModulus(int value1, int value2)
{
    while (value1 != 0 && value2 != 0)
    {
        if (value1 > value2)
            value1 %= value2;
        else
            value2 %= value1;
    }
    return Math.Max(value1, value2);
}

Obtaining the GCD Using Recursion

The final version of Euclid's algorithm uses recursion to obtain the result. This is beneficial when using functional programming languages, such as F#. However, I will describe it here using C# for completeness.

The recursive method has two possible outcomes. If the second value is zero, the first value is the GCD and is returned. If the second value is not zero, the method is called again. The new call passes the second value, which is assumed to be the lower number, and the modulus of the first and second integers. Each call progressively lowers the values until the GCD is found. Note that although the second value is assumed to be lower it need not be. If the second integer is greater than the first the initial call will swap the values.

public static int GetGCDRecursively(int value1, int value2)
{
    if (value2 == 0)
        return value1;
    else
        return GetGCDRecursively(value2, value1 % value2);
}