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\$
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\$
  • 1
    \$\begingroup\$ What about the built-in Integer#gdc? It's cheating, I know :) \$\endgroup\$ – Flambino Sep 6 '16 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 Sep 6 '16 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 Sep 6 '16 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\$
  • 3
    \$\begingroup\$ This is a code dump with no explanation, and only mildly different from @tokland's answer. \$\endgroup\$ – 200_success Sep 23 '16 at 18:45
  • 1
    \$\begingroup\$ @200_success I see nothing to add here. The question is too simple. The code is minimal. \$\endgroup\$ – Nakilon Sep 23 '16 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 Sep 23 '16 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 Oct 11 '18 at 14:32
  • \$\begingroup\$ Stop the mindless comments spam cancer. My answers are explained enough. \$\endgroup\$ – Nakilon Oct 11 '18 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\$
  • 3
    \$\begingroup\$ Please explain why this solution is better than the one posted in the question. \$\endgroup\$ – Null Oct 10 '18 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 Oct 11 '18 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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