Calculate Greatest Common Divisor (GCD) of more than two values

Question

In VB.NET or C#, I would like to be able calculate the Greatest Common Divisor (GCD) of one or more values, dynamically, and without using recursive methodology.

I took as a guideline this solution in C# to calculate the GCD of two values. Now, I would like to adapt that solution to be able calculate an undetermined amount of values (one or more values that are contained in a array of values passed to the function below)...

This is what I did by the moment:

VB.NET (original code):

<DebuggerStepperBoundary>
Private Shared Function InternalGetGreatestCommonDivisor(ParamArray values As Integer()) As Integer

    ' Calculate GCD for 2 or more values...
    If (values.Length > 1) Then
        Do While Not values.Contains(0)
            For Each value As Integer In values
                Dim firstMaxValue As Integer = values.Max()
                Dim secondMaxValue As Integer = values.OrderByDescending(Function(int As Integer) int)(1)
                values(values.ToList.IndexOf(firstMaxValue)) = (firstMaxValue Mod secondMaxValue)
            Next value
        Loop

        Return If(values.Contains(0), values.Max(), values.Min())

    Else ' Calculate GCD for a single value...
        Return ...

    End If

End Function

C# (online code conversion, I didn't tested it at all):

[DebuggerStepperBoundary]
private static int InternalGetGreatestCommonDivisor(params int[] values)
{

    // Calculate GCD for 2 or more values...
    if (values.Length > 1)
    {
        while (!values.Contains(0))
        {
            foreach (int value in values)
            {
                int firstMaxValue = values.Max();
                int secondMaxValue = values.OrderByDescending((int @int) => @int).ElementAtOrDefault(1);
                values[values.ToList().IndexOf(firstMaxValue)] = (firstMaxValue % secondMaxValue);
            }
        }

        return (values.Contains(0) ? values.Max() : values.Min());

    }
    else // Calculate GCD for a single value...
    {
        return ...;

}

I'm aware that the type conversion to List would affect overall performance for a large amount of values, but the most priority thing is to make this algorithm work as expected, and finally optimize/refactorize it.

My adaptation works as expected for some combinations of values, but it does not work for anothers. For example in this online GCD calculator, if we put these values: {1920, 1080, 5000, 1000, 6800, 5555} in theory the GCD is 5, or at least that is the GCD calculated by that online service, but my algorithm returns 15.

Why would you do this type of loop "For Each value As Integer In values" when you don't use the variable "value"? — the_lotus, Dec 04 '18 at 15:53
@the_lotus I'm aware the design is wrong, that is the reason why I'm asking. However, the loop was just to do a full loop iteration, rather than using each iterated value. Im getting closer (proper in most cases) GCD doing that. But I know it is wrong, I insist. Thanks for comment. — ElektroStudios, Dec 04 '18 at 15:59
@Milster please take into account: "C# (online code conversion, I didn't tested it at all)". Anyway I'll edit/remove that part of the source-code since the positive value conversion it is not necessary at all to show a code sample. Thanks for comment. — ElektroStudios, Dec 04 '18 at 16:00
`gcd(a, b, c) = gcd(a, gcd(b, c))`. This means that if you have a `gcd` function that works for two arguments, you can lift it to a collection using LINQ's `Enumerable.Aggregate`. That does not involve recursion, and optimizing it (if necessary) is probably as simple as sorting the collection. — Jeroen Mostert, Dec 04 '18 at 16:02
@Jeroen Mostert Many thanks for the tip. Just to clarify it, you are literally saying to do this?: https://stackoverflow.com/a/3635650/1248295 I tried it and aparently it works fine. But it would be really necessary to sort the values following that solution?. — ElektroStudios, Dec 04 '18 at 16:08
Sort of, except that I wouldn't write `GCD2` recursively, as the elegant non-recursive implementation is quite literally [the oldest algorithm in the book](https://en.wikipedia.org/wiki/Euclidean_algorithm). And no, sorting the values is not required at all for correctness, but using the Euclidean algorithm you may want to "optimize" the order to ensure the minimum number of operations. I wouldn't start off with optimizing anything unless this is demonstrably necessary. — Jeroen Mostert, Dec 04 '18 at 16:09
@ElektroStudios Your problem is hidden here: `Do While Not values.Contains(0)`. You are aborting too early. Check if all but one value is zero and leave then. The last value above 0 is the one you are looking for. And get rid of the useless foreach of course. — Milster, Dec 04 '18 at 16:12

score 1 · Answer 1 · answered Dec 04 '18 at 16:36

// pass all the values in array and call findGCD function
    int findGCD(int arr[], int n) 
    { 
        int gcd = arr[0]; 
        for (int i = 1; i < n; i++) {
            gcd = getGcd(arr[i], gcd); 
}

        return gcd; 
    } 

// check for gcd
int getGcd(int x, int y) 
    { 
        if (x == 0) 
            return y; 
        return gcd(y % x, x); 
    }

score 0 · Answer 2 · answered Dec 04 '18 at 16:07

0

You can do this using Linq:

    static int GCD2(int a, int b){
        return b == 0 ? Math.Abs(a) : GCD2(b, a % b);
    }

    static int GCD(int[] numbers){
        return numbers.Aggregate(GCD2);
    }

answered Dec 04 '18 at 16:07

Turkey

21
4

Thank you, but that has recursion. I would accept the answer it if you modify the "GCD2" function to be non-recursive (if you would like to do a copy-and-paste of this: https://stackoverflow.com/a/41766138/1248295 , for example. ) – ElektroStudios Dec 04 '18 at 16:11

score 0 · Accepted Answer · answered Dec 04 '18 at 16:25

The issue you are facing is caused by the fact that you are leaving the inner loop too early. Checking if any value is 0 is not enough, as you actually have to check if all but one value is 0.

The C# code could look like this:

private static int InternalGetGreatestCommonDivisor(params int[] values)
{
    // Calculate GCD for 2 or more values...
    if (values.Length > 1)
    {
      while (values.Count(value => value > 0) != 1)
      {
          int firstMaxValue = values.Max();
          int secondMaxValue = values.OrderByDescending((int @int) => @int).ElementAtOrDefault(1);
          values[values.ToList().IndexOf(firstMaxValue)] = (firstMaxValue % secondMaxValue);
      }

      return values.Max();

    }
    else
    {
      // Calculate GCD for a single value...
    }

}

The code returns 5 for your example. I'm afraid I can't give you the exact representation for the VB.NET code.

Calculate Greatest Common Divisor (GCD) of more than two values

3 Answers3