Euclidean algorithm (GCD) with multiple numbers?

by

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.

More Related Contents:

  1. Does Python IDE have a module which imports math functions such as cos or sin? [closed]
  2. What is the difference between ‘/’ and ‘//’ when used for division?
  3. Why does the division get rounded to an integer?
  4. How can I check for NaN values?
  5. Python math is wrong [duplicate]
  6. Integer square root in python
  7. How do you print superscript in Python?
  8. How do I do exponentiation in python? [duplicate]
  9. How did Python implement the built-in function pow()?
  10. C and Python – different behaviour of the modulo (%) operation
  11. Algorithm to find which number in a list sum up to a certain number
  12. Why do “Not a Number” values equal True when cast as boolean in Python/Numpy?
  13. How to make scipy.interpolate give an extrapolated result beyond the input range?
  14. How can I randomly choose a maths operator and ask recurring maths questions with it?
  15. Integer division by negative number [duplicate]
  16. numpy arbitrary precision linear algebra
  17. Can someone explain this: 0.2 + 0.1 = 0.30000000000000004? [duplicate]
  18. Python Math – TypeError: ‘NoneType’ object is not subscriptable
  19. How to get all combination of n binary value? [duplicate]
  20. how can i show an irrational number to 100 decimal places in python?
  21. How do order of operations go on Python?
  22. Rotate point about another point in degrees python
  23. Computing Standard Deviation in a stream
  24. Inaccurate Logarithm in Python
  25. Function to determine if two numbers are nearly equal when rounded to n significant decimal digits
  26. What’s the simplest way to extend a numpy array in 2 dimensions?
  27. Rounding floats so that they sum to precisely 1
  28. math.sin incorrect result
  29. counting combinations and permutations efficiently
  30. Convert Latitude and Longitude to point in 3D space

Leave a Comment