Calculating GCD for 2 integers











up vote
5
down vote

favorite












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









share|improve this question
























  • (Document&) Comment your code.
    – greybeard
    Aug 19 '17 at 17:26










  • If they don't enter an integer it fails
    – paparazzo
    Aug 19 '17 at 17:33















up vote
5
down vote

favorite












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









share|improve this question
























  • (Document&) Comment your code.
    – greybeard
    Aug 19 '17 at 17:26










  • If they don't enter an integer it fails
    – paparazzo
    Aug 19 '17 at 17:33













up vote
5
down vote

favorite









up vote
5
down vote

favorite











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









share|improve this 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);
}
}






c# algorithm






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Aug 19 '17 at 21:24









Jamal

30.2k11115226




30.2k11115226










asked Aug 19 '17 at 17:21









Gustaf Linder

403




403












  • (Document&) Comment your code.
    – greybeard
    Aug 19 '17 at 17:26










  • If they don't enter an integer it fails
    – paparazzo
    Aug 19 '17 at 17:33


















  • (Document&) Comment your code.
    – greybeard
    Aug 19 '17 at 17:26










  • If they don't enter an integer it fails
    – paparazzo
    Aug 19 '17 at 17:33
















(Document&) Comment your code.
– greybeard
Aug 19 '17 at 17:26




(Document&) Comment your code.
– greybeard
Aug 19 '17 at 17:26












If they don't enter an integer it fails
– paparazzo
Aug 19 '17 at 17:33




If they don't enter an integer it fails
– paparazzo
Aug 19 '17 at 17:33










5 Answers
5






active

oldest

votes

















up vote
6
down vote



accepted










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.






share|improve this answer




























    up vote
    7
    down vote













    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.






    share|improve this answer



















    • 2




      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.
      – greybeard
      Aug 20 '17 at 8:30






    • 3




      @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.
      – Tristan Gibson
      Aug 20 '17 at 11:42










    • the second recursive suggestion would benefit a lot from dropping the unnecessary else
      – Vogel612
      Aug 21 '17 at 8:28


















    up vote
    5
    down vote













    A Recursive solution would be much cleaner.



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





    share|improve this answer





















    • That is slick +1
      – paparazzo
      Aug 20 '17 at 16:28


















    up vote
    0
    down vote













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





    share|improve this answer

















    • 2




      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.)
      – greybeard
      Aug 19 '17 at 19:10


















    up vote
    -1
    down vote













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





    share|improve this answer



















    • 1




      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).
      – user673679
      Dec 8 at 13:09











    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "196"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f173413%2fcalculating-gcd-for-2-integers%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    5 Answers
    5






    active

    oldest

    votes








    5 Answers
    5






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    6
    down vote



    accepted










    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.






    share|improve this answer

























      up vote
      6
      down vote



      accepted










      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.






      share|improve this answer























        up vote
        6
        down vote



        accepted







        up vote
        6
        down vote



        accepted






        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.






        share|improve this answer












        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.







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered Aug 19 '17 at 19:10









        janos

        96.7k12124350




        96.7k12124350
























            up vote
            7
            down vote













            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.






            share|improve this answer



















            • 2




              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.
              – greybeard
              Aug 20 '17 at 8:30






            • 3




              @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.
              – Tristan Gibson
              Aug 20 '17 at 11:42










            • the second recursive suggestion would benefit a lot from dropping the unnecessary else
              – Vogel612
              Aug 21 '17 at 8:28















            up vote
            7
            down vote













            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.






            share|improve this answer



















            • 2




              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.
              – greybeard
              Aug 20 '17 at 8:30






            • 3




              @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.
              – Tristan Gibson
              Aug 20 '17 at 11:42










            • the second recursive suggestion would benefit a lot from dropping the unnecessary else
              – Vogel612
              Aug 21 '17 at 8:28













            up vote
            7
            down vote










            up vote
            7
            down vote









            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.






            share|improve this answer














            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.







            share|improve this answer














            share|improve this answer



            share|improve this answer








            edited Feb 12 at 22:50

























            answered Aug 19 '17 at 19:12









            Tristan Gibson

            11510




            11510








            • 2




              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.
              – greybeard
              Aug 20 '17 at 8:30






            • 3




              @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.
              – Tristan Gibson
              Aug 20 '17 at 11:42










            • the second recursive suggestion would benefit a lot from dropping the unnecessary else
              – Vogel612
              Aug 21 '17 at 8:28














            • 2




              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.
              – greybeard
              Aug 20 '17 at 8:30






            • 3




              @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.
              – Tristan Gibson
              Aug 20 '17 at 11:42










            • the second recursive suggestion would benefit a lot from dropping the unnecessary else
              – Vogel612
              Aug 21 '17 at 8:28








            2




            2




            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.
            – greybeard
            Aug 20 '17 at 8:30




            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.
            – greybeard
            Aug 20 '17 at 8:30




            3




            3




            @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.
            – Tristan Gibson
            Aug 20 '17 at 11:42




            @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.
            – Tristan Gibson
            Aug 20 '17 at 11:42












            the second recursive suggestion would benefit a lot from dropping the unnecessary else
            – Vogel612
            Aug 21 '17 at 8:28




            the second recursive suggestion would benefit a lot from dropping the unnecessary else
            – Vogel612
            Aug 21 '17 at 8:28










            up vote
            5
            down vote













            A Recursive solution would be much cleaner.



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





            share|improve this answer





















            • That is slick +1
              – paparazzo
              Aug 20 '17 at 16:28















            up vote
            5
            down vote













            A Recursive solution would be much cleaner.



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





            share|improve this answer





















            • That is slick +1
              – paparazzo
              Aug 20 '17 at 16:28













            up vote
            5
            down vote










            up vote
            5
            down vote









            A Recursive solution would be much cleaner.



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





            share|improve this answer












            A Recursive solution would be much cleaner.



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






            share|improve this answer












            share|improve this answer



            share|improve this answer










            answered Aug 19 '17 at 18:40









            omaraloraini

            39535




            39535












            • That is slick +1
              – paparazzo
              Aug 20 '17 at 16:28


















            • That is slick +1
              – paparazzo
              Aug 20 '17 at 16:28
















            That is slick +1
            – paparazzo
            Aug 20 '17 at 16:28




            That is slick +1
            – paparazzo
            Aug 20 '17 at 16:28










            up vote
            0
            down vote













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





            share|improve this answer

















            • 2




              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.)
              – greybeard
              Aug 19 '17 at 19:10















            up vote
            0
            down vote













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





            share|improve this answer

















            • 2




              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.)
              – greybeard
              Aug 19 '17 at 19:10













            up vote
            0
            down vote










            up vote
            0
            down vote









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





            share|improve this answer












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






            share|improve this answer












            share|improve this answer



            share|improve this answer










            answered Aug 19 '17 at 18:51









            milbrandt

            34715




            34715








            • 2




              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.)
              – greybeard
              Aug 19 '17 at 19:10














            • 2




              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.)
              – greybeard
              Aug 19 '17 at 19:10








            2




            2




            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.)
            – greybeard
            Aug 19 '17 at 19:10




            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.)
            – greybeard
            Aug 19 '17 at 19:10










            up vote
            -1
            down vote













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





            share|improve this answer



















            • 1




              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).
              – user673679
              Dec 8 at 13:09















            up vote
            -1
            down vote













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





            share|improve this answer



















            • 1




              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).
              – user673679
              Dec 8 at 13:09













            up vote
            -1
            down vote










            up vote
            -1
            down vote









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





            share|improve this answer














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






            share|improve this answer














            share|improve this answer



            share|improve this answer








            edited Dec 8 at 13:19









            Sᴀᴍ Onᴇᴌᴀ

            8,13861752




            8,13861752










            answered Dec 8 at 10:45









            Chang

            71




            71








            • 1




              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).
              – user673679
              Dec 8 at 13:09














            • 1




              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).
              – user673679
              Dec 8 at 13:09








            1




            1




            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).
            – user673679
            Dec 8 at 13:09




            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).
            – user673679
            Dec 8 at 13:09


















            draft saved

            draft discarded




















































            Thanks for contributing an answer to Code Review Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f173413%2fcalculating-gcd-for-2-integers%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Сан-Квентин

            Алькесар

            Josef Freinademetz