## "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()
```