• Post Reply Bookmark Topic Watch Topic
  • New Topic

Using Euclid's Algorithm To Find GCD  RSS feed

 
Christopher McKay
Ranch Hand
Posts: 50
Android Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?

 
Paul Clapham
Sheriff
Posts: 22823
43
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:

 
Christopher McKay
Ranch Hand
Posts: 50
Android Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Euclid's algorithm is a classic recursive algorithm. Have you considered trying to implement this with recursion? It's incredibly compact.
 
Christopher McKay
Ranch Hand
Posts: 50
Android Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Paul Clapham
Sheriff
Posts: 22823
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!