Calculating GCD for 2 integers

Question

I have implemented a method which takes 2 numbers and returns the Greatest Common Divisor, using the Euclidean algorithm.

The Euclidean algorithm goes like this:

If we take the numbers 585 and 442:

585 / 442 = 1 (remainder 143)

442 / 143 = 3 (remainder 13)

143 / 13 = 11 (remainder 0)

The process stops here and GCD = 13.

Is there any way I can make this implementation better, considering time, resources and refactoring?

using System;

class Program
{
    static void Main()
    {
        Console.WriteLine("Input first number: ");
        int x = Convert.ToInt32(Console.ReadLine());
        Console.WriteLine("Input second number: ");
        int y = Convert.ToInt32(Console.ReadLine());

        Console.WriteLine(GetGCD(x, y));

        Console.ReadKey();
    }

    static int GetGCD(int x, int y)
    {
        while (Math.Max(x, y) % Math.Min(x, y) != 0)
        {
            int tmp = Math.Max(x, y) % Math.Min(x, y);
            if (x < y) y = tmp;
            else x = tmp;
        }

        return Math.Min(x, y);
    }
}

Answer 1

The implementation of GetGCD is more complicated than it needs to be. The Math.Max and Math.Min wastefully evaluate x < y more than needed, because when you know that x is the max, you also know that y is the min. And you perform these multiple times per iteration, and in addition to that x < y one more time.

Consider this alternative:

static int gcd(int x, int y)
{
    while (y != 0)
    {
        int tmp = x % y;
        x = y;
        y = tmp;
    }

    return x;
}

You don't need to worry about whether x or y is bigger. It's ideal when x > y, but if it isn't, this algorithm swaps them. The only cost is one more iteration of the loop, but this is still cheaper than what you had previously with all the Math.Max and Math.Min.

Answer 2

Recursive Method

You can change your GetGCD() method to be much more intuitive and minimal using a ternary operator and recursion. I recommend also documenting what it's doing for readability purposes:

static int GetGCD(int x, int y)
{
    // If y is equal to 0, return x.
    // If y is not equal to 0, recursive call with x as y and y as the remainder.
    return y == 0 ? x : GetGCD(y, x % y);
}

Can also be written as:

static int GetGCD(int x, int y)
{
    // If y is equal to 0, return x.
    if (y == 0)
        return x;
    // If y is not equal to 0, recursive call with x as y and y as the remainder.
    return GetGCD(y, x % y);
}

Depending on your preference.

Iterative Method

As stated in other answers, you might use an iterative method:

static int GetGCD(int x, int y)
{
    while (y != 0)
    {
        int tmp = x % y;
        x = y;
        y = tmp;
    }
    return x;
}

Entry Point

Use TryParse() for retrieving integer input from the console. We don't want exceptions on user input.

Modular arithmetic should be positive. To ensure this, we use the absolute value of the input (Euclidean division). Here's how I would implement it:

static void Main()
{
    int x, y;

    // Get x. Ensure it's an integer.
    Console.WriteLine("Input first number: ");
    while(!Int32.TryParse(Console.ReadLine(), out x));

    // Get y. Ensure it's an integer.
    Console.WriteLine("Input second number: ");
    while(!Int32.TryParse(Console.ReadLine(), out y));

    // Ensure the values being used are positive.
    Console.WriteLine(GetGCD(Math.Abs(x), Math.Abs(y)));

    Console.ReadKey();
}

Output

As you can see, it will wait for an input that can be parsed to an integer and returns the expected value:

Input first number: 
a
b
c
585
Input second number: 
d
442
13

Benchmark

Just for fun, I thought I'd test the difference between the recursive and iterative methods.

Benchmarked method: Recursive
Test cases: 20
Bench in MS: 184
Iterations per case: 10000000

Benchmarked method: Iterative
Test cases: 20
Bench in MS: 121
Iterations per case: 10000000

The difference is negligible in real application (unless you plan to run this millions of times). These tests were run from entirely different processes.

Answer 3

A Recursive solution would be much cleaner.

int Gcd(int x, int y) => y == 0 ? x : Gcd(y, x % y);

Answer 4

Use TryParse to avoid fails if not an integer is entered.

static void Main()
{
    Console.WriteLine("Input first number: ");
    int x;
    while (!Int32.TryParse(Console.ReadLine(), out x)) ;
    Console.WriteLine("Input second number: ");
    int y;
    while (!Int32.TryParse(Console.ReadLine(), out y)) ;

    Console.WriteLine(GetGCD(x, y));

    Console.ReadKey();
}

Avoid double max, min and modululo calculation in GDC.

static int GetGCD(int x, int y)
{
    int tmp;
    while ((tmp = Math.Max(x, y) % Math.Min(x, y)) != 0)
    {
        if (x < y) y = tmp;
        else x = tmp;
    }

    return Math.Min(x, y);
}

Answer 5

By using this, you can pass multiple values as well in the form of array:-

// 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); 
    }