24
\$\begingroup\$
def gcd(a,b):
    if (a>b):
        r1=a
        r2=b
    else:
        r1=b
        r2=a   
    if(r1%r2==0):
        print (r2)
    else:
        gcd(r2, r1%r2)
a= int(input("Enter a number"))
b= int(input("Enter a number"))
gcd(a,b)

This code is about finding the greatest common divisor of two numbers. Are there any better methods? How can I improve this code?

\$\endgroup\$
  • 13
    \$\begingroup\$ "Are there any better methods? " According to some definitions of "better": from math import gcd \$\endgroup\$ – John Coleman May 9 '18 at 13:10
31
\$\begingroup\$
  • Bug:

    When I input -6 and -3 I expect the result to be 3 but I get a RecursionError exception instead:

    RecursionError: maximum recursion depth exceeded in comparison
    
  • For the sake of UX:

    • Leave some space between the text you display and the data to input:

      Enter a number6
      Enter a number5
      

      This would be the minimum better:

      Enter a number: 6
      Enter a number: 5
      
    • You know what your program does, but not the user, so your messages must be clear and precise. Ask the user not to input a number but an integer number. Otherwise this can mislead the user to input a real number, or input a character by mistake (or even try to break into your software):

      Traceback (most recent call last):
        File "cr.py", line 12, in <module>
          a= int(input("Enter a number"))
      ValueError: invalid literal for int() with base 10: 'g'
      
    • Your program does not give a choice for the user to exit. The minimum you can do for this purpose is to handle the KeyboardInterrupt exception corresponding to when the user presses Ctrl + c

    • The messages are intended to communicate with the user, so let him know what the programs does:

      print('Computing the GCD of two numbers.\n')
      
  • Divide and conquer:

    This is a consequence of the aformentioned: it is time to implement a function whose only purpose is care about the user's input:

    def read_an_integer_user_input():
        a = None   
        while type(a) != int:
            try:
                a = int(input('Enter an integer: '))
            except ValueError:
                print('I expect an integer value. Try again.')
            except KeyboardInterrupt:
                print('\nGoodbye!')
                break
        return a
    
  • Do not print, return:

    We expect the function that computes something to return the result not to print it. Not only this is the function definition by essence, but this way you give more chance for your code to be reused and properly. So instead of coding print(r2) I would write return r2; by the way, do not leave space between print and (.

  • Iterative version:

    Given the recursion bug previsouly mentioned, I would opt for an iterative implementation of your code:

    def compute_gcd(a,b):
        a = abs(a)
        b = abs(b)
        while b:
            a, b = b, a%b
        return a
    

Full program:

Let us gather the elements above to build a small coherent program:

def compute_gcd(a,b):
    a = abs(a)
    b = abs(b)
    while b:
        a, b = b, a%b
    return a

def read_an_integer_user_input():
   a = None   
   while type(a) != int:
       try:
           a = int(input('Enter an integer: '))
       except ValueError:
           print('I expect an integer value. Try again.')
       except KeyboardInterrupt:
           print('\nGoodbye!')
           break
   return a

if __name__ == '__main__':
    print('Computing the GCD of two numbers.')
    a = read_an_integer_user_input()
    b = read_an_integer_user_input()
    if a and b:       
       print('The GCD of {} and {} is: {}'.format(a, b, compute_gcd(a, b)))
\$\endgroup\$
  • 10
    \$\begingroup\$ I like this answer except the use of type which is rarely needed. Can't you use while True: try: return int(…) … instead? \$\endgroup\$ – Mathias Ettinger May 9 '18 at 7:30
  • \$\begingroup\$ You are right about that, your approach is better. Keep your comment so that the OP can compare and find out there are always rooms to improve. \$\endgroup\$ – Billal Begueradj May 9 '18 at 7:37
  • \$\begingroup\$ “Given the recursion bug previsouly mentioned, I would opt for an iterative implementation of your code” — This statement doesn’t make sense. Your iterative code fixes the bug in the recursive version, but so would a correct recursive code. And you could also write a buggy iterative implementation. \$\endgroup\$ – Konrad Rudolph May 9 '18 at 10:57
  • \$\begingroup\$ I agree with you but: 1. As other mentioned, large numbers in the recursive version may lead to other serious bugs. 2. The OP says he is open for other methods @KonradRudolph \$\endgroup\$ – Billal Begueradj May 9 '18 at 11:08
  • 1
    \$\begingroup\$ You only need to take the absolute value at the end: def compute_gcd(a,b):\n while b:\n a,b = b,a%b\n return abs(a) \$\endgroup\$ – 12Me21 May 9 '18 at 13:50
19
\$\begingroup\$

Python has an official style-guide, PEP8. It recommends (among other things) the following:

  • Use whitespace around operators (so a = input(...)).
  • Don't use unnecessary parenthesis (if, for, while, etc don't need any)

In addition to this, you should make your function return the result rather than printing. Otherwise you cannot use it in further calculations:

g = gcd(10, 15)
# 5
print(g)
# None
g + 1
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

With these I would change your code to:

def gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    return gcd(b, a % b)

Normally, I would point out that this approach has the inherent problem of all recursive solutions in Python, the stack limit (by default 1000). However, due to the fact of always continuing with a % b in the recursion, this function works even for large coprime numbers:

gcd(16956998685025525617332092680088906859010597516989049974644188276809460728386128015966080402491132114558031760245789600047216269236212122151725198496639367,
    130219041176878297644835828972023265387463111246248427493495319607240172982284)
# 1

And finally, as for alternative approaches, there exists already a gcd function in the built-in math module (since Python 3.5). Since it is implemented in C it is a bit faster than this function that is limited to run entirely in Python:

In [5]: a = 16956998685025525617332092680088906859010597516989049974644188276809460728386128015966080402491132114558031760245789600047216269236212122151725198496639367
In [6]: b = 130219041176878297644835828972023265387463111246248427493495319607240172982284
In [7]: %timeit gcd(a, b)
57.1 µs ± 590 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [8]: %timeit math_gcd(a, b)
2.99 µs ± 6.66 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

The iterative function from the answer by @BillalBEGUERADJ clocks in somewhere in the middle between the two:

In [14]: %timeit compute_gcd(a, b)
17.9 µs ± 316 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
\$\endgroup\$
  • 2
    \$\begingroup\$ Prior to 3.5, there is fractions.gcd. \$\endgroup\$ – Gareth Rees May 9 '18 at 6:33
  • \$\begingroup\$ @Graipher you could improve your gcd function's speed by 20% or more (not tried it) by assigning the result of "a % b" rather than recalculating it. \$\endgroup\$ – Konchog May 9 '18 at 7:30
  • 1
    \$\begingroup\$ @Konchog Yes, that shaves off about 10%. But since both the iterative approach and the built-in one are faster it is probably not worth it to make it slightly harder to read. \$\endgroup\$ – Graipher May 9 '18 at 7:32
  • \$\begingroup\$ @Gaipher, of course built-in is faster - but it's not much of a code review! If we are going to use a recursive, then yours is a good answer - but by using eg "return c == 0 ? b : gcd(b, c)" on the last line the code is nominally more efficient and just as readable. \$\endgroup\$ – Konchog May 9 '18 at 8:04
13
\$\begingroup\$

If you want to know whether there are more efficient algorithms than Euclid's, this is probably the wrong place to ask. Even Wikipedia would be a better starting point. The answer is yes but they are far more complicated. Intuitively I'd ignore Stein's algorithm (on that page as "Binary GCD algorithm") for Python because it relies on low level tricks like bit shifts that Python really doesn't excel at. Euclid's algorithm is probably fine.

In terms of your implementation of the Euclidean algorithm

  • You don't need to manually check which of a and b is greater. If they're the wrong way round, the first % operation will swap them for you.
  • You should have your function return a value rather than print a value. Print can be called from outside.
  • You should consider how you'll handle negative numbers. As written this will give a negative GCD for (-5 and 10). It will crash for (5 and -10). The right answer is probably 5.
\$\endgroup\$
5
\$\begingroup\$

Let’s go back to basics for a minute.

What’s the definition of the Euclidean algorithm?

First off, the algorithm only contains a single precondition:

Numbers must be positive.

Nothing about the order of a and b is mentioned, making the first six lines of your function redundant:

def gcd(r1, r2):
    if r1 % r2 == 0:
        print(r2)
    else:
        gcd(r2, r1 % r2)

(I’ve also formatted the code in accordance with PEP8, mentioned previously.)

Next, the stop condition of the algorithm isn’t that r1 % r2 == 0. It is:

a remainder rN must eventually equal zero, at which point the algorithm stops

So we only need to test if r2 == 0, saving us one computation:

def gcd(r1, r2):
    if r2 == 0:
        print(r1)
    else:
        gcd(r2, r1 % r2)

This is as far as we are going to take the algorithm itself for now. Now for some more general remarks:

Functions should either compute a result, or handle I/O. Never both. So return the GCD instead:

def gcd(r1, r2):
    if r2 == 0:
        return r1
    else:
        return gcd(r2, r1 % r2)

This function consists of a single test with two return statements. It’s idiomatic to rewrite such statements into a single return statement with a conditional value:

def gcd(r1, r2):
    return r1 if r2 == 0 else gcd(r2, r1 % r2)

These last two forms are large equivalent. Some people (me included) find the second version more readable but in Python I can see how one might disagree, due to Python’s syntax: other languages write if a then b else c, or a ? b : c; Python, by contrast, forces you to write b if a else c; what?!

Now, although the recursive form of this algorithm is idiomatic and elegant, it’s true this isn’t pythonic: Python (mostly due to its main developer’s whim rather than technical reasons) eschews recursion in favour of iteration.

Luckily the iterative form in this case is likewise elegant and relatively simple: it hinges on the recognition that the recursive algorithm progressively swaps the values of the remainders with the next remainder in the series (although now the variable names are even more misleading: we should really be using rN and rN+1:

def gcd(r1, r2):
    while r2 != 0:
        r1, r2 = r2, r1 % r2
    return r1

Bonus: Note that all the above implementations implicitly rely on the precondition: they yield wrong results with negative input. Luckily, we can extend the implementation trivially to handle negative inputs, and the good news is: we don’t need to modify the inputs in any way. We simply need to make the output positive:

def gcd(r1, r2):
    while r2 != 0:
        r1, r2 = r2, r1 % r2
    return abs(r1)

And of course the same also works on the recursive form:

def gcd(r1, r2):
    return abs(r1) if r2 == 0 else gcd(r2, r1 % r2)
\$\endgroup\$
  • 1
    \$\begingroup\$ If you want the gcd always to be non-negative (which is by no means a universal convention), then you need to sprinkle in an absolute value somewhere. (EDIT: Sorry, I just noticed this is done in your final two versions.) Otherwise, I appreciate your bringing up these elegant simplifications; I was itching while reading the detailed style guides that missed the algorithmic overcomplication! \$\endgroup\$ – LSpice May 10 '18 at 0:59
  • 1
    \$\begingroup\$ bool(r2 != 0) <=> bool(r2) \$\endgroup\$ – Mathias Ettinger May 10 '18 at 16:38
  • \$\begingroup\$ @MathiasEttinger Please no. Be explicit with what you meant: we don’t want to convert a value to bool. We want to compare a value to zero. In fact, it’s a good general policy to be suspicious of conversions. Note how the comparison doesn’t need a conversion, and putting bool around it has no effect. \$\endgroup\$ – Konrad Rudolph May 10 '18 at 17:26
  • \$\begingroup\$ @KonradRudolph I was using bool to denote that both expressions are equivalent in a boolean context (your ifs and whiles) not to use it in the code. The point is that r2 may be anything and, if fed with an erroneous object, it's better to let the code fail at the relevant mathematical operation rather than an (arbitrary) comparison. \$\endgroup\$ – Mathias Ettinger May 10 '18 at 17:41
  • \$\begingroup\$ @MathiasEttinger Fair enough but I still disagree. Truthy values are great for some things but they always come at the cost of explicitness, and in this particular case I want to (and, I claim, any programmer should want to) be explicit about what mathematical operation is performed here. In the context of my code, I’m not looking at truthy values, I’m operating on specific values of integers. The fact that a truthiness test happens to yield the correct result here is a pure accident. \$\endgroup\$ – Konrad Rudolph May 10 '18 at 17:54
2
\$\begingroup\$

Your implementation is recursive, which means you can get a stack overflow for numbers which require a large depth. As the algorithm is a tail recursion you can convert it to a loop, which does not suffer from this problem.

\$\endgroup\$
  • 4
    \$\begingroup\$ As shown in other answers, this is a purely theoretical concern. \$\endgroup\$ – Konrad Rudolph May 9 '18 at 11:04
  • 1
    \$\begingroup\$ While this may be a theoretical problem (like in "for small n everything is O(1)"), we are here to review code to be better than before and thus it is useful to point out these problems as well. OP does not need to change this, but they may consider this issue. \$\endgroup\$ – allo May 10 '18 at 11:38
2
\$\begingroup\$

Stack overflow isn't a purely theoretical concern; I was able to cause one with:

70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

and

113796925398360272257523782552224175572745930353730513145086634176691092536145985470146129334641866902783673042322088625863396052888690096969577173696370562180400527049497109023054114771394568040040412172632376

(consecutive Fibonacci numbers)

\$\endgroup\$
  • 2
    \$\begingroup\$ It works for me in Python 3. \$\endgroup\$ – Konrad Rudolph May 9 '18 at 16:41
-2
\$\begingroup\$
#--input
a = int(input("Enter a number: "))
print() # new line
b = int(input("Enter a number: "))
print() # new line

#--check/make a > b only once
if (b > a):
    a,b = b,a

#--one simple loop for GCD 
while(a%b != 0):
    x,a = a,b
    b = x%b

#--If one or both values are negative
if(b < 0):
    b *= -1

print ("GCD = ", b)

Try this. It has one small loop for GCD. And -ve value correction. I've added comments to describe the code.

\$\endgroup\$
  • 3
    \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$ – Vogel612 May 10 '18 at 9:21
  • 2
    \$\begingroup\$ In addition to being a terrible answer, this is terrible code 1) the question is tagged python-3.x so check your prints 2) check your indentation, this is no valid Python 3) swapping values should be a one-liner thanks to tupple unpacking 4) parentheses around comparisons are an unnecessary clutter 5) be consistent in your spacing around operators (and read PEP8) 6) use better, descriptive, variables names 7) you removed the one thing that was great in the original code: a function definition \$\endgroup\$ – Mathias Ettinger May 11 '18 at 18:02
  • 1
    \$\begingroup\$ You still don't refer to the code in the question in any way: down-voted. \$\endgroup\$ – greybeard May 21 '18 at 8:41
  • \$\begingroup\$ @MathiasEttinger, what's wrong with the indentation? \$\endgroup\$ – Anton Sherwood Jun 18 '18 at 19:24
  • \$\begingroup\$ @AntonSherwood post has been edited since the comment, this point has been fixed. \$\endgroup\$ – Mathias Ettinger Jun 18 '18 at 19:28

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.