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)  

util.py
Go to the documentation of this file.
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
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 
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()
nzmath.factor.util.FactoringInteger.factors
factors
Definition: util.py:150
nzmath.factor.util.FactoringInteger.getMatchingFactor
def getMatchingFactor(self, number)
Definition: util.py:208
nzmath.factor.util.FactoringInteger.setPrimality
def setPrimality(self, number, isprime)
Definition: util.py:254
nzmath.gcd
Definition: gcd.py:1
nzmath.factor.util.FactoringMethod._getVerbose
def _getVerbose(self)
Definition: util.py:130
nzmath.factor.util.FactoringInteger.getNextTarget
def getNextTarget(self, cond=None)
Definition: util.py:231
nzmath.factor.util.FactoringMethod.find
def find(self, target, **options)
Definition: util.py:99
nzmath.factor.util.FactoringMethod.generate
def generate(self, target, **options)
Definition: util.py:110
nzmath.factor.util.FactoringInteger.sortFactors
def sortFactors(self)
Definition: util.py:260
nzmath.factor.util.FactoringInteger.replace
def replace(self, number, factors)
Definition: util.py:185
nzmath.factor.util.FactoringInteger.register
def register(self, divisor, isprime=Unknown)
Definition: util.py:153
nzmath.factor.util.FactoringInteger.primality
primality
Definition: util.py:151
nzmath.factor.util.FactoringMethod.continue_factor
def continue_factor(self, tracker, **options)
Definition: util.py:49
nzmath.factor.util.FactoringMethod.factor
def factor(self, number, **options)
Definition: util.py:19
nzmath.factor.util.FactoringMethod._validate_input_number
def _validate_input_number(number)
Definition: util.py:86
nzmath.factor.util.FactoringMethod._setVerbose
def _setVerbose(self, boolean)
Definition: util.py:134
nzmath.arith1
Definition: arith1.py:1
nzmath.factor.util.FactoringInteger.number
number
Definition: util.py:149
nzmath.prime
Definition: prime.py:1
nzmath.prime.primeq
def primeq(n)
Definition: prime.py:380
nzmath.factor.util.FactoringInteger.getResult
def getResult(self)
Definition: util.py:248
nzmath.factor.util.FactoringInteger
Definition: util.py:141
nzmath.factor.util.FactoringInteger.getCompositeFactor
def getCompositeFactor(self)
Definition: util.py:218
nzmath.factor.util.FactoringMethod.__init__
def __init__(self)
Definition: util.py:15
nzmath.factor.util.FactoringInteger.__init__
def __init__(self, number)
Definition: util.py:145
nzmath.factor.util.FactoringMethod._verbose
_verbose
Definition: util.py:17
nzmath.factor.util.FactoringMethod
Definition: util.py:11