NZMATH  1.2.0
About: NZMATH is a Python based number theory oriented calculation system.
  Fossies Dox: NZMATH-1.2.0.tar.gz  ("inofficial" and yet experimental doxygen-generated source code documentation)  

gcd.py
Go to the documentation of this file.
1 """
2 funtions related to the greatest common divisor of integers.
3 """
4 
5 import nzmath.arygcd as arygcd
6 
7 def gcd(a, b):
8  """
9  Return the greatest common divisor of 2 integers a and b.
10  """
11  a, b = abs(a), abs(b)
12  while b:
13  a, b = b, a % b
14  return a
15 
16 def binarygcd(a, b):
17  """
18  Return the greatest common divisor of 2 integers a and b
19  by binary gcd algorithm.
20  """
21  # use arygcd version
22  a, b = abs(a), abs(b)
23  return arygcd.binarygcd(a, b)
24 
25 def extgcd(x, y):
26  """
27  Return a tuple (u, v, d); they are the greatest common divisor d
28  of two integers x and y and u, v such that d = x * u + y * v.
29  """
30  # Crandall & Pomerance "PRIME NUMBERS", Algorithm 2.1.4
31  a, b, g, u, v, w = 1, 0, x, 0, 1, y
32  while w:
33  q, t = divmod(g, w)
34  a, b, g, u, v, w = u, v, w, a-q*u, b-q*v, t
35  if g >= 0:
36  return (a, b, g)
37  else:
38  return (-a, -b, -g)
39 
40 def gcd_of_list(integers):
41  """
42  Return a list [d, [c1, ..., cn]] for a list of integers [x1, ..., xn]
43  such that d = c1 * x1 + ... + cn * xn.
44  """
45  the_gcd = 0
46  total_length = len(integers)
47  coeffs = []
48  coeffs_length = 0
49  for integer in integers:
50  multiplier, new_coeff, the_gcd = extgcd(the_gcd, integer)
51  if multiplier != 1:
52  for i in range(coeffs_length):
53  coeffs[i] *= multiplier
54  coeffs.append(new_coeff)
55  coeffs_length += 1
56  if the_gcd == 1:
57  coeffs.extend([0] * (total_length - coeffs_length))
58  break
59  return [the_gcd, coeffs]
60 
61 def lcm(a, b):
62  """
63  Return the least common multiple of given 2 integers.
64  If both are zero, it raises an exception.
65  """
66  return a // gcd(a, b) * b
67 
68 def coprime(a, b):
69  """
70  Return True if a and b are coprime, False otherwise.
71 
72  For Example:
73  >>> coprime(8, 5)
74  True
75  >>> coprime(-15, -27)
76  False
77  >>>
78  """
79  return gcd(a, b) == 1
80 
81 def pairwise_coprime(int_list):
82  """
83  Return True if all integers in int_list are pairwise coprime,
84  False otherwise.
85 
86  For example:
87  >>> pairwise_coprime([1, 2, 3])
88  True
89  >>> pairwise_coprime([1, 2, 3, 4])
90  False
91  >>>
92  """
93  int_iter = iter(int_list)
94  product = int_iter.next()
95  for n in int_iter:
96  if not coprime(product, n):
97  return False
98  product *= n
99  return True
nzmath.bigrange.range
def range(start, stop=None, step=None)
Definition: bigrange.py:19
nzmath.gcd.extgcd
def extgcd(x, y)
Definition: gcd.py:25
nzmath.gcd.coprime
def coprime(a, b)
Definition: gcd.py:68
nzmath.gcd.binarygcd
def binarygcd(a, b)
Definition: gcd.py:16
nzmath.gcd.gcd
def gcd(a, b)
Definition: gcd.py:7
nzmath.gcd.gcd_of_list
def gcd_of_list(integers)
Definition: gcd.py:40
nzmath.arygcd
Definition: arygcd.py:1
nzmath.gcd.pairwise_coprime
def pairwise_coprime(int_list)
Definition: gcd.py:81
nzmath.gcd.lcm
def lcm(a, b)
Definition: gcd.py:61