6
\$\begingroup\$

I am trying to implement a algorithm for the GCD of two numbers in a functional approach. Can this be improved further, also with regards to performance?

def gcd(a, b)
   return b if a ==0
   return a if b == 0
   return b if (a%b == 0)
   return a if (b%a == 0)
  (a > b)? gcd(a, a%b) : gcd(b%a, b)
end
\$\endgroup\$
0

3 Answers 3

Reset to default
15
\$\begingroup\$

It does not matter whether a > b or b > a, two cases should be enough for positive integers:

def gcd(a, b)
  b == 0 ? a : gcd(b, a.modulo(b))
end

Check also Integer#gcd.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ What about the built-in Integer#gdc? It's cheating, I know :) \$\endgroup\$
    – Flambino
    Commented Sep 6, 2016 at 11:50
  • 1
    \$\begingroup\$ By the way, maybe use .zero? instead of == 0? Either way is equally fine to my eyes, it's just to mention it \$\endgroup\$
    – Flambino
    Commented Sep 6, 2016 at 11:52
  • 1
    \$\begingroup\$ @Flambino: Good point, although I guess the OP knows about Integer#gdc and it's a pedagogical question. b.zero? would also look good, since I am already using modulo instead of %. \$\endgroup\$
    – tokland
    Commented Sep 6, 2016 at 12:07
2
\$\begingroup\$ 
def gcd a, b
  return a if b.zero?
  gcd b, a % b
end

Avoid ?: when the <return/next/break> if <condition> form can be used.

\$\endgroup\$
5
  • 3
    \$\begingroup\$ This is a code dump with no explanation, and only mildly different from @tokland's answer. \$\endgroup\$
    – 200_success
    Commented Sep 23, 2016 at 18:45
  • 1
    \$\begingroup\$ @200_success I see nothing to add here. The question is too simple. The code is minimal. \$\endgroup\$
    – Nakilon
    Commented Sep 23, 2016 at 18:47
  • \$\begingroup\$ I've added a one line of text to it. Totally pointless line. Because the code edit is trivial. It's just nothing to comment here. The answer was much clearer without this line. \$\endgroup\$
    – Nakilon
    Commented Sep 23, 2016 at 19:09
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$
    – Toby Speight
    Commented Oct 11, 2018 at 14:32
  • \$\begingroup\$ Stop the mindless comments spam cancer. My answers are explained enough. \$\endgroup\$
    – Nakilon
    Commented Oct 11, 2018 at 14:40
0
\$\begingroup\$

I've came up with this one:

def gcd(a, b)
  a, b = b, a % b until b.zero?
  a
end
\$\endgroup\$
2
  • 3
    \$\begingroup\$ Please explain why this solution is better than the one posted in the question. \$\endgroup\$
    – Null
    Commented Oct 10, 2018 at 22:58
  • \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$
    – Toby Speight
    Commented Oct 11, 2018 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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