Python program to calculate GCD

Question

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?

Answer 1

• 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)))

Answer 2

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)

Answer 3

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.

Answer 4

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 r_N 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 r_N and r_N+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)

Answer 5

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.

Answer 6

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

70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

and

113796925398360272257523782552224175572745930353730513145086634176691092536145985470146129334641866902783673042322088625863396052888690096969577173696370562180400527049497109023054114771394568040040412172632376

(consecutive Fibonacci numbers)

Answer 7

#--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.