"Fossies" - the Fresh Open Source Software Archive

Member "NZMATH-1.2.0/nzmath/factor/util.py" (19 Nov 2012, 9164 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 "util.py" see the Fossies "Dox" file reference documentation.

    1 """
    2 factor.util -- utility module for factorization.
    3 """
    4 
    5 import nzmath.arith1 as arith1
    6 import nzmath.gcd as gcd
    7 import nzmath.prime as prime
    8 
    9 Unknown = None
   10 
   11 class FactoringMethod (object):
   12     """
   13     Base class of factoring methods.
   14     """
   15     def __init__(self):
   16         # verbosity
   17         self._verbose = False
   18 
   19     def factor(self, number, **options):
   20         """
   21         Factor the given positive integer.
   22 
   23         The default returned type is a list of tuples.  Each tuple has
   24         a factor and its valuation, and the product is equal to the
   25         given number.  It looks like:
   26           [(p1, e1), ..., (pn, en)].
   27 
   28         an option 'return_type' is for the returned type, whose value can be:
   29         1) 'list' for default type described above.
   30         2) 'tracker' for FactoringInteger.
   31 
   32         an option 'need_sort' is boolean: True to sort the result.
   33         This should be specified with return_type='list'.
   34         """
   35         if not self._validate_input_number(number):
   36             return []
   37 
   38         tracker = FactoringInteger(number)
   39         for p, e in self.generate(number, **options):
   40             if p != 1:
   41                 tracker.register(p, True)
   42         if options.get('return_type', 'list') == 'list':
   43             result = tracker.getResult()
   44             if options.get('need_sort', False):
   45                 return sorted(result)
   46             return result
   47         return tracker
   48 
   49     def continue_factor(self, tracker, **options):
   50         """
   51         Continue factoring and return the result of factorization.
   52 
   53         The argument 'tracker' should be an instance of FactoringInteger.
   54 
   55         The default returned type is FactoringInteger, but if
   56         'return_type' is specified as 'list' then it returns
   57         list of tuples (prime, index).
   58         The primes are judged by a function specified in 'primeq'
   59         optional argument, default to nzmath.prime.primeq.
   60         """
   61         return_list = (options.get('return_type', '') == 'list')
   62         primeq = options.get('primeq', prime.primeq)
   63 
   64         while True:
   65             try:
   66                 target = tracker.getNextTarget()
   67             except LookupError:
   68                 # factored completely
   69                 break
   70             if primeq(target):
   71                 tracker.register(target, True)
   72             else:
   73                 p = self.find(target, **options)
   74                 if 1 < p < target:
   75                     # factor found
   76                     tracker.register(p, primeq(p))
   77                 elif p == 1:
   78                     # failed to factor
   79                     break
   80         if return_list:
   81             return tracker.getResult()
   82         else:
   83             return tracker
   84 
   85     @staticmethod
   86     def _validate_input_number(number):
   87         """
   88         Return True if the given number is an integer greater than one.
   89         Return False if the given number is equal to one.
   90         Otherwise, raise ValueError.
   91         """
   92         if isinstance(number, (int, long)):
   93             if number == 1:
   94                 return False
   95             if number > 1:
   96                 return True
   97         raise ValueError("number must be a positive integer.")
   98 
   99     def find(self, target, **options):
  100         """
  101         Find a factor from the target number.  The method may return 1
  102         to indicate the factorization is incomplete.
  103 
  104         This method must be overridden, or 'factor' method should be
  105         overridden not to call this method.
  106         """
  107         for p, e in self.generate(target, **options):
  108             return p
  109 
  110     def generate(self, target, **options):
  111         """
  112         Generate prime factors of the target number with their
  113         valuations.  The method may terminate with yielding (1, 1)
  114         to indicate the factorization is incomplete.
  115 
  116         This method must be overridden, or 'factor' method should be
  117         overridden not to call this method.
  118         """
  119         tracker = FactoringInteger(target)
  120         options['return_type'] = 'tracker'
  121         result = self.continue_factor(tracker, **options)
  122         for p, e in result.factors:
  123             if result.primality[p]:
  124                 yield p, e
  125                 target //= p ** e
  126             else:
  127                 yield 1, 1
  128                 break
  129 
  130     def _getVerbose(self):
  131         "getter for property verbose"
  132         return self._verbose
  133 
  134     def _setVerbose(self, boolean):
  135         "setter for property verbose"
  136         self._verbose = boolean
  137 
  138     verbose = property(_getVerbose, _setVerbose, None, "Verbosity: boolean")
  139 
  140 
  141 class FactoringInteger (object):
  142     """
  143     A class for keeping track of factorization.
  144     """
  145     def __init__(self, number):
  146         """
  147         The given number must be a composite.
  148         """
  149         self.number = number
  150         self.factors = [(number, 1)]
  151         self.primality = {number:False}
  152 
  153     def register(self, divisor, isprime=Unknown):
  154         """
  155         Register a divisor of the number, if the divisor is a true
  156         divisor of the number.  The number is divided by the divisor
  157         as many times as possible.
  158         """
  159         for base, index in self.factors:
  160             if base == divisor:
  161                 if isprime and not self.primality[base]:
  162                     self.setPrimality(base, isprime)
  163                 break
  164             common_divisor = gcd.gcd(base, divisor)
  165             if common_divisor == 1:
  166                 continue
  167             # common_divisor > 1:
  168             if common_divisor == divisor:
  169                 if isprime:
  170                     self.setPrimality(divisor, isprime)
  171                 k, coprime = arith1.vp(base, common_divisor)
  172                 while not gcd.coprime(common_divisor, coprime):
  173                     # try a smaller factor
  174                     common_divisor = gcd.gcd(common_divisor, coprime)
  175                     k, coprime = arith1.vp(base, common_divisor)
  176                 if k:
  177                     if coprime > 1:
  178                         self.replace(base, [(common_divisor, k), (coprime, 1)])
  179                     else:
  180                         self.replace(base, [(common_divisor, k)])
  181             else: # common_divisor properly divides divisor.
  182                 self.register(common_divisor)
  183                 self.register(divisor // common_divisor)
  184 
  185     def replace(self, number, factors):
  186         """
  187         Replace a number with factors.
  188         The number is a one of known factors of tracked number.
  189         factors is a list of (base, index) pairs.
  190         It is assumed that number = product of factors.
  191         """
  192         try:
  193             replacee = self.getMatchingFactor(number)
  194             self.factors.remove(replacee)
  195             if replacee[0] in self.primality:
  196                 del self.primality[replacee[0]]
  197             replacee_index = replacee[1]
  198             for base, index in factors:
  199                 if replacee_index == 1:
  200                     self.factors.append((base, index))
  201                 else:
  202                     self.factors.append((base, index * replacee_index))
  203                 if base not in self.primality:
  204                     self.setPrimality(base, Unknown)
  205         except LookupError:
  206             raise ValueError("no factor matches to %d." % number)
  207 
  208     def getMatchingFactor(self, number):
  209         """
  210         Find a factor matching to number.
  211         """
  212         # use linear search because self.factors is a short list.
  213         for base, index in self.factors:
  214             if base == number:
  215                 return (base, index)
  216         raise LookupError("no factor matches.")
  217 
  218     def getCompositeFactor(self):
  219         """
  220         Return a composite (or unknown primality) factor from factors
  221         in a form (base, index), whose base's primality is non-True.
  222 
  223         If there is no such factor, LookupError will be raised.
  224         """
  225         # use linear search because self.factors is a short list.
  226         for base, index in self.factors:
  227             if not self.primality[base]:
  228                 return (base, index)
  229         raise LookupError("no factor matches.")
  230 
  231     def getNextTarget(self, cond=None):
  232         """
  233         Return the next target which meets 'cond'.  if 'cond' is not
  234         specified, then the next target is a composite (or unknown
  235         primality) factor of self.number.  'cond' can be a binary
  236         (arguments are base and index) predicate.
  237 
  238         If there is no such factor, LookupError will be raised.
  239         """
  240         if cond is None:
  241             cond = lambda base, index: not self.primality[base]
  242         # use linear search because self.factors is a short list.
  243         for base, index in self.factors:
  244             if cond(base, index):
  245                 return base
  246         raise LookupError("no factor matches.")
  247 
  248     def getResult(self):
  249         """
  250         Return the factors in the form of [(base, index), ...].
  251         """
  252         return list(self.factors)
  253 
  254     def setPrimality(self, number, isprime):
  255         """
  256         Set primality for number to isprime.
  257         """
  258         self.primality[number] = isprime
  259 
  260     def sortFactors(self):
  261         """
  262         Sort factors list. Return nothing.
  263         """
  264         if len(self.factors) > 1:
  265             self.factors.sort()