posted 3 years ago

After learning about Euclid's Algorithm for finding the greatest common divisor of 2 integers, I decided to make a demo program in Java. My questions are: Is the following code good/efficient, and how can it be improved?

posted 3 years ago

- 1

I was confused about the if-statement in lines 5 to 8. After staring at it for a while I figured out that its purpose was to make num1 the larger of the two parameters and num2 the smaller. I would have been spared all that if you had called the variables "larger" and "smaller", or something like that, rather than "num1" and "num2".

And then you have a variable named "product", which given the context sounded to me like you were multiplying numbers together. Perhaps "result" would be a better name.

And then you've got a "previousProduct" variable which you initialize to number1. Choosing the number1 variable as the initial value led me to wonder why you chose that until I noticed that it didn't matter. But with a little code change you don't need to pre-initialize the variable at all.

Point being, variable names are important. Make them meaningful. Here's my revised code based on that advice:

And then you have a variable named "product", which given the context sounded to me like you were multiplying numbers together. Perhaps "result" would be a better name.

And then you've got a "previousProduct" variable which you initialize to number1. Choosing the number1 variable as the initial value led me to wonder why you chose that until I noticed that it didn't matter. But with a little code change you don't need to pre-initialize the variable at all.

Point being, variable names are important. Make them meaningful. Here's my revised code based on that advice:

posted 3 years ago

Thanks, I should have noticed that 'previousResult' didn't need to be pre-initialized. Also, sorry about the variable naming, I will make sure in future to try keep variable names useful :)

Paul Clapham wrote:I was confused about the if-statement in lines 5 to 8. After staring at it for a while I figured out that its purpose was to make num1 the larger of the two parameters and num2 the smaller. I would have been spared all that if you had called the variables "larger" and "smaller", or something like that, rather than "num1" and "num2".

And then you have a variable named "product", which given the context sounded to me like you were multiplying numbers together. Perhaps "result" would be a better name.

And then you've got a "previousProduct" variable which you initialize to number1. Choosing the number1 variable as the initial value led me to wonder why you chose that until I noticed that it didn't matter. But with a little code change you don't need to pre-initialize the variable at all.

Point being, variable names are important. Make them meaningful. Here's my revised code based on that advice:

Thanks, I should have noticed that 'previousResult' didn't need to be pre-initialized. Also, sorry about the variable naming, I will make sure in future to try keep variable names useful :)

Matthew Brown

Bartender

Posts: 4568

9

posted 3 years ago

Sorry, I don't quite understand what you mean, could you give me an example?

EDIT: Looked up some examples and recursion is definitely the way to go with this algorithm. Thanks for suggesting recursion!

Matthew Brown wrote:Euclid's algorithm is a classic recursive algorithm. Have you considered trying to implement this with recursion? It's incredibly compact.

Sorry, I don't quite understand what you mean, could you give me an example?

EDIT: Looked up some examples and recursion is definitely the way to go with this algorithm. Thanks for suggesting recursion!

Matthew Brown

Bartender

Posts: 4568

9

posted 3 years ago

A recursive method is one that calls itself (with different parameters, so that eventually it terminates). If you look at the definition of Euclid's algorithm - e.g. http://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid.27s_algorithm - it can be defined like this:

That can be almost directly translated into a method body. Check if

- 1

Christopher McKay wrote:Sorry, I don't quite understand what you mean, could you give me an example?

A recursive method is one that calls itself (with different parameters, so that eventually it terminates). If you look at the definition of Euclid's algorithm - e.g. http://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid.27s_algorithm - it can be defined like this:

gcd(a,0) = a

gcd(a,b) = gcd(b, a mod b)

That can be almost directly translated into a method body. Check if

`b`is zero, and return one of the two expressions.

posted 3 years ago

Just one other comment about improvements: Your code assumes that the parameters passed to it are positive integers. If this is not the case then unexpected things will happen, and it's even possible for the code to crash. So in real-life environments you might want to put some code in at the beginning which checks that the parameters are indeed positive, and if they aren't then does something else. What that "something else" might be depends on the context in which the method is used, but throwing an IllegalArgumentException might be the right thing to do in many cases.