"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:

    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