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);
}
}
c# algorithm
add a comment |
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);
}
}
c# algorithm
(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
add a comment |
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);
}
}
c# algorithm
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
c# algorithm
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
add a comment |
(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
add a comment |
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
.
add a comment |
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.
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 unnecessaryelse
– Vogel612♦
Aug 21 '17 at 8:28
add a comment |
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);
That is slick +1
– paparazzo
Aug 20 '17 at 16:28
add a comment |
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);
}
2
For every iteration, this callsMath.Max()
andMin
; it comparesx
toy
just once less. (I'm not in the mood to consider negativey
andx
.) Just use variables likegreater
andsmaller
- no need to check after initialising (andremainder
). (Every time I see the function nameGetGCD()
I like it less.)
– greybeard
Aug 19 '17 at 19:10
add a comment |
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);
}
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 functiongcd
is not defined).
– user673679
Dec 8 at 13:09
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
.
add a comment |
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
.
add a comment |
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
.
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
.
answered Aug 19 '17 at 19:10
janos
96.7k12124350
96.7k12124350
add a comment |
add a comment |
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.
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 unnecessaryelse
– Vogel612♦
Aug 21 '17 at 8:28
add a comment |
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.
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 unnecessaryelse
– Vogel612♦
Aug 21 '17 at 8:28
add a comment |
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.
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.
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 unnecessaryelse
– Vogel612♦
Aug 21 '17 at 8:28
add a comment |
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 unnecessaryelse
– 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
add a comment |
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);
That is slick +1
– paparazzo
Aug 20 '17 at 16:28
add a comment |
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);
That is slick +1
– paparazzo
Aug 20 '17 at 16:28
add a comment |
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);
A Recursive solution would be much cleaner.
int Gcd(int x, int y) => y == 0 ? x : Gcd(y, x % y);
answered Aug 19 '17 at 18:40
omaraloraini
39535
39535
That is slick +1
– paparazzo
Aug 20 '17 at 16:28
add a comment |
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
add a comment |
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);
}
2
For every iteration, this callsMath.Max()
andMin
; it comparesx
toy
just once less. (I'm not in the mood to consider negativey
andx
.) Just use variables likegreater
andsmaller
- no need to check after initialising (andremainder
). (Every time I see the function nameGetGCD()
I like it less.)
– greybeard
Aug 19 '17 at 19:10
add a comment |
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);
}
2
For every iteration, this callsMath.Max()
andMin
; it comparesx
toy
just once less. (I'm not in the mood to consider negativey
andx
.) Just use variables likegreater
andsmaller
- no need to check after initialising (andremainder
). (Every time I see the function nameGetGCD()
I like it less.)
– greybeard
Aug 19 '17 at 19:10
add a comment |
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);
}
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);
}
answered Aug 19 '17 at 18:51
milbrandt
34715
34715
2
For every iteration, this callsMath.Max()
andMin
; it comparesx
toy
just once less. (I'm not in the mood to consider negativey
andx
.) Just use variables likegreater
andsmaller
- no need to check after initialising (andremainder
). (Every time I see the function nameGetGCD()
I like it less.)
– greybeard
Aug 19 '17 at 19:10
add a comment |
2
For every iteration, this callsMath.Max()
andMin
; it comparesx
toy
just once less. (I'm not in the mood to consider negativey
andx
.) Just use variables likegreater
andsmaller
- no need to check after initialising (andremainder
). (Every time I see the function nameGetGCD()
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
add a comment |
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);
}
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 functiongcd
is not defined).
– user673679
Dec 8 at 13:09
add a comment |
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);
}
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 functiongcd
is not defined).
– user673679
Dec 8 at 13:09
add a comment |
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);
}
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);
}
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 functiongcd
is not defined).
– user673679
Dec 8 at 13:09
add a comment |
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 functiongcd
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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
(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