## "Fossies" - the Fresh Open Source Software Archive ### Member "NZMATH-1.2.0/nzmath/gcd.py" (19 Nov 2012, 2390 Bytes) of package /linux/misc/old/NZMATH-1.2.0.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Python source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file. For more information about "gcd.py" see the Fossies "Dox" file reference documentation.

```    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( * (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
```