Euclidean algorithm (GCD) with multiple numbers?

Question

So I'm writing a program in Python to get the GCD of any amount of numbers.

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]


    # i'm stuck here, this is wrong
    for i in range(len(numbers)-1):
        print GCD([numbers[i+1], numbers[i] % numbers[i+1]])


print GCD(30, 40, 36)

The function takes a list of numbers. This should print 2. However, I don't understand how to use the the algorithm recursively so it can handle multiple numbers. Can someone explain?

updated, still not working:

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]

    gcd = 0

    for i in range(len(numbers)):
        gcd = GCD([numbers[i+1], numbers[i] % numbers[i+1]])
        gcdtemp = GCD([gcd, numbers[i+2]])
        gcd = gcdtemp

    return gcd

---

Ok, solved it

def GCD(a, b):

    if b == 0:
        return a
    else:
        return GCD(b, a % b)

and then use reduce, like

reduce(GCD, (30, 40, 36))

Utimer

your first problem that I notice is that you will need to sort the list so that the smallest element is the last – Felting

Not sure if duplicate or just related: Computing greatest common denominator in python – Adulate

just fyi if you can do it with iterative instead of recurse it would probably be faster and able to handle larger values ... recursion of undefined depth can be a little sketchy in python – Felting

Answer 1

Since GCD is associative, GCD(a,b,c,d) is the same as GCD(GCD(GCD(a,b),c),d). In this case, Python's reduce function would be a good candidate for reducing the cases for which len(numbers) > 2 to a simple 2-number comparison. The code would look something like this:

if len(numbers) > 2:
    return reduce(lambda x,y: GCD([x,y]), numbers)

Reduce applies the given function to each element in the list, so that something like

gcd = reduce(lambda x,y:GCD([x,y]),[a,b,c,d])

is the same as doing

gcd = GCD(a,b)
gcd = GCD(gcd,c)
gcd = GCD(gcd,d)

Now the only thing left is to code for when len(numbers) <= 2. Passing only two arguments to GCD in reduce ensures that your function recurses at most once (since len(numbers) > 2 only in the original call), which has the additional benefit of never overflowing the stack.

Chukchi

Answer 2

You can use reduce:

>>> from fractions import gcd
>>> reduce(gcd,(30,40,60))
10

which is equivalent to;

>>> lis = (30,40,60,70)
>>> res = gcd(*lis[:2])  #get the gcd of first two numbers
>>> for x in lis[2:]:    #now iterate over the list starting from the 3rd element
...    res = gcd(res,x)

>>> res
10

help on reduce:

>>> reduce?
Type:       builtin_function_or_method
reduce(function, sequence[, initial]) -> value

Apply a function of two arguments cumulatively to the items of a sequence,
from left to right, so as to reduce the sequence to a single value.
For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
((((1+2)+3)+4)+5).  If initial is present, it is placed before the items
of the sequence in the calculation, and serves as a default when the
sequence is empty.

Sabra

While technically correct and absolutely the version I would prefer, I don't think it will help him understand why it works, as the solution is 'hidden' in the definition of reduce. – Rasputin

i'm not going to use an already made gcd function though, i want to learn – Utimer

Answer 3

Python 3.9 introduced multiple arguments version of math.gcd, so you can use:

import math
math.gcd(30, 40, 36)

---

3.5 <= Python <= 3.8.x:

import functools
import math
functools.reduce(math.gcd, (30, 40, 36))

---

3 <= Python < 3.5:

import fractions
import functools
functools.reduce(fractions.gcd, (30, 40, 36))

Certify

Answer 4

A solution to finding out the LCM of more than two numbers in PYTHON is as follow:

#finding LCM (Least Common Multiple) of a series of numbers

def GCD(a, b):
    #Gives greatest common divisor using Euclid's Algorithm.
    while b:      
        a, b = b, a % b
    return a

def LCM(a, b):
    #gives lowest common multiple of two numbers
    return a * b // GCD(a, b)

def LCMM(*args):
    #gives LCM of a list of numbers passed as argument 
    return reduce(LCM, args)

Here I've added +1 in the last argument of range() function because the function itself starts from zero (0) to n-1. Click the hyperlink to know more about range() function :

print ("LCM of numbers (1 to 5) : " + str(LCMM(*range(1, 5+1))))
print ("LCM of numbers (1 to 10) : " + str(LCMM(*range(1, 10+1))))
print (reduce(LCMM,(1,2,3,4,5)))

those who are new to python can read more about reduce() function by the given link.

Coracorabel

Answer 5

The GCD operator is commutative and associative. This means that

gcd(a,b,c) = gcd(gcd(a,b),c) = gcd(a,gcd(b,c))

So once you know how to do it for 2 numbers, you can do it for any number

---

To do it for two numbers, you simply need to implement Euclid's formula, which is simply:

// Ensure a >= b >= 1, flip a and b if necessary
while b > 0
  t = a % b
  a = b
  b = t
end
return a

Define that function as, say euclid(a,b). Then, you can define gcd(nums) as:

if (len(nums) == 1)
  return nums[1]
else
  return euclid(nums[1], gcd(nums[:2]))

This uses the associative property of gcd() to compute the answer

Lagniappe

Then why don't you use that knowledge? Generate gcd for one pair, and work your way through your list with the above properties of gcd. – Rasputin

Take the gcd of the first number with the second, save the result to a variable. get the next number of the list, get the gcd of the previously saved result together with the new value. repeat until end of list. the value of your variable is the gcd of all numbers together. – Rasputin

@Rasputin updated my post with your solution that I don't know how to implement – Utimer

Answer 6

Try calling the GCD() as follows,

i = 0
temp = numbers[i]
for i in range(len(numbers)-1):
        temp = GCD(numbers[i+1], temp)

Petersham

Answer 7

My way of solving it in Python. Hope it helps.

def find_gcd(arr):
    if len(arr) <= 1:
        return arr
    else:
        for i in range(len(arr)-1):
            a = arr[i]
            b = arr[i+1]
            while b:
                a, b = b, a%b
            arr[i+1] = a
        return a
def main(array):
    print(find_gcd(array))

main(array=[8, 18, 22, 24]) # 2
main(array=[8, 24]) # 8
main(array=[5]) # [5]
main(array=[]) # []

Some dynamics how I understand it:

ex.[8, 18] -> [18, 8] -> [8, 2] -> [2, 0]

18 = 8x + 2 = (2y)x + 2 = 2z where z = xy + 1

ex.[18, 22] -> [22, 18] -> [18, 4] -> [4, 2] -> [2, 0]

22 = 18w + 4 = (4x+2)w + 4 = ((2y)x + 2)w + 2 = 2z

Weismann

Answer 8

As of python 3.9 beta 4, it has got built-in support for finding gcd over a list of numbers.

Python 3.9.0b4 (v3.9.0b4:69dec9c8d2, Jul  2 2020, 18:41:53)
[Clang 6.0 (clang-600.0.57)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import math
>>> A = [30, 40, 36]
>>> print(math.gcd(*A))
2

Salpiglossis

Answer 9

One of the issues is that many of the calculations only work with numbers greater than 1. I modified the solution found here so that it accepts numbers smaller than 1. Basically, we can re scale the array using the minimum value and then use that to calculate the GCD of numbers smaller than 1.

# GCD of more than two (or array) numbers - alows folating point numbers
# Function implements the Euclidian algorithm to find H.C.F. of two number 
def find_gcd(x, y): 
    while(y): 
        x, y = y, x % y 
    return x 
          
# Driver Code         
l_org = [60e-6, 20e-6, 30e-6]
min_val = min(l_org)
l = [item/min_val for item in l_org]
  
num1 = l[0] 
num2 = l[1] 
gcd = find_gcd(num1, num2) 
  
for i in range(2, len(l)): 
    gcd = find_gcd(gcd, l[i]) 
      
gcd = gcd * min_val
print(gcd) 

Ogdoad

Answer 10

HERE IS A SIMPLE METHOD TO FIND GCD OF 2 NUMBERS

a = int(input("Enter the value of first number:"))
b = int(input("Enter the value of second number:"))
c,d = a,b
while a!=0:
    b,a=a,b%a
print("GCD of ",c,"and",d,"is",b)

Lohman

Answer 11

As You said you need a program who would take any amount of numbers and print those numbers' HCF.

In this code you give numbers separated with space and click enter to get GCD

num =list(map(int,input().split()))  #TAKES INPUT
def print_factors(x):          #MAKES LIST OF LISTS OF COMMON FACTROS OF INPUT
    list = [ i for i in range(1, x + 1) if x % i == 0 ]
    return list

p = [print_factors(numbers) for numbers in num]
result = set(p[0])        
for s in p[1:]:             #MAKES THE SET OF COMMON VALUES IN LIST OF LISTS
    result.intersection_update(s)

for values in result:
    values = values*values     #MULTIPLY ALL COMMON FACTORS TO FIND GCD
    values = values//(list(result)[-1])  
print('HCF',values)

Hope it helped

Oeuvre