5
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ (Document&) Comment your code. \$\endgroup\$ – greybeard Aug 19 '17 at 17:26
  • \$\begingroup\$ If they don't enter an integer it fails \$\endgroup\$ – paparazzo Aug 19 '17 at 17:33
6
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ no need to create tmp every iteration - kidding? "Creating" an instance of a value type is no effort, if not a misconception. Keeping scopes as small as possible is a virtue. \$\endgroup\$ – greybeard Aug 20 '17 at 8:30
  • 3
    \$\begingroup\$ @greybeard You are correct, the IL produced is (probably) exactly the same. Upon verifying this, it is stated that "stack space for local variables is usually allocated in the function scope." There would be no overhead and the benefit of declaring within the scope would be readability and convenience. Thank you for correcting me; it's indeed a misconception I had. \$\endgroup\$ – Tristan Gibson Aug 20 '17 at 11:42
  • \$\begingroup\$ the second recursive suggestion would benefit a lot from dropping the unnecessary else \$\endgroup\$ – Vogel612 Aug 21 '17 at 8:28
5
\$\begingroup\$

A Recursive solution would be much cleaner.

int Gcd(int x, int y) => y == 0 ? x : Gcd(y, x % y);
\$\endgroup\$
  • \$\begingroup\$ That is slick +1 \$\endgroup\$ – paparazzo Aug 20 '17 at 16:28
0
\$\begingroup\$

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);
}
\$\endgroup\$
  • 2
    \$\begingroup\$ For every iteration, this calls Math.Max() and Min; it compares x to y just once less. (I'm not in the mood to consider negative y and x.) Just use variables like greater and smaller - no need to check after initialising (and remainder). (Every time I see the function name GetGCD() I like it less.) \$\endgroup\$ – greybeard Aug 19 '17 at 19:10
-1
\$\begingroup\$

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); 
    } 
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to codereview. For alternative solution answers, it's important to include some explanation of why the alternative provided is better. This answer does not address the code in the question, and also does not work (the function gcd is not defined). \$\endgroup\$ – user673679 Dec 8 '18 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.