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) formalsum.py
Go to the documentation of this file.
1 """
2 formalsum --- formal sum, or linear combination.
3
4 The formalsum is mathematically a finite sum of terms.
5 The term consists of two parts: coefficient and base.
6 The coefficients must be in a ring. The base is arbitrary.
7
8 Two formalsums can be added in the following way.
9 If there are terms with common base, they are fused into a
10 new term with the same base and coefficients added.
11
12 A coefficient can be looked up from the base.
13 If the specified base does not appear in the formalsum,
14 it is null.
15
16 abstract data type FS:
17  FS: list(tuple(B, C)) -> FS
18
19  +: FS x FS -> FS
20  FS -> FS
21  -: FS x FS -> FS
22  FS -> FS
23  *: C x FS -> FS
24  FS x C -> FS
25
26  []: FS x B -> C
27  bases: FS -> list(B)
28  coefficeints: FS -> list(C)
29  terms: FS -> list(tuple(B, C))
30  ==: FS x FS -> bool
31  !=: FS x FS -> bool
32  len: FS -> int
33  repr: FS -> str
34 """
35
37
38
40  """
41  Interface of formal sum container.
42  Do not instantiate.
43  """
44  def __iter__(self):
45  """
46  Return the iterator.
47  It is an alias of iterterms.
48  """
49  return self.iterterms()
50
51  def __getitem__(self, base):
52  """
53  Return the coefficient of specified base.
54  If there is no term of the base, return 0.
55  """
56  raise NotImplementedError("method '__getitem__' must be overridden")
57
58  def __contains__(self, base):
59  """
60  base in self
61
62  membership test.
63  """
64  return base in self.bases()
65
66  def __len__(self):
67  """
68  Return the number of data entries.
69  """
70  raise NotImplementedError("method '__len__' must be overridden")
71
72  def __eq__(self, other):
73  """
74  self == other
75
76  This implementaion is not optimal for more structured
77  descendants.
78  """
79  if self is other:
80  return True
81  if not isinstance(other, FormalSumContainerInterface):
82  return False
83  self_bases = set(self.iterbases())
84  other_bases = set(other.iterbases())
85  if self_bases != other_bases:
86  return False
87  for base in self_bases:
88  if self[base] != other[base]:
89  return False
90  return True
91
92  def __hash__(self):
93  val = sum([hash(self[base]) for base in set(self.iterbases())])
94  return val
95
96  def __ne__(self, other):
97  """
98  self != other
99  """
100  return not self.__eq__(other)
101
102  def __nonzero__(self):
103  """
104  Return True, if self has some nonzero coefficients.
105  False, otherwise.
106  """
107  for c in self.itercoefficients():
108  if c:
109  return True
110  return False
111
112  def __hash__(self):
113  """
114  hash(self)
115  """
116  try:
117  return sum([hash(b)*hash(c) for (b, c) in self]) & 0x7fff
118  except TypeError:
119  raise TypeError("unhashable")
120
122  """
123  self + other
124  """
125  sum_coeff = dict(self.iterterms())
126  for base, coeff in other:
127  if base in sum_coeff:
128  sum_coeff[base] += coeff
129  else:
130  sum_coeff[base] = coeff
131  return self.construct_with_default([(b, c) for (b, c) in sum_coeff.iteritems() if c])
132
133  def __sub__(self, other):
134  """
135  self - other
136  """
137  sub_coeff = dict(self.iterterms())
138  for base, coeff in other:
139  if base in sub_coeff:
140  sub_coeff[base] -= coeff
141  else:
142  sub_coeff[base] = -coeff
143  return self.construct_with_default([(b, c) for (b, c) in sub_coeff.iteritems() if c])
144
145  def __neg__(self):
146  """
147  -self
148  """
149  raise NotImplementedError("method '__neg__' should be overridden")
150
151  def __pos__(self):
152  """
153  +self
154  """
155  raise NotImplementedError("method '__pos__' should be overridden")
156
157  def __mul__(self, other):
158  """
159  self * other
160
161  Only scalar multiplication is defined.
162  """
163  raise NotImplementedError("method '__mul__' should be overridden")
164
165  def __rmul__(self, other):
166  """
167  other * self
168
169  This method is invoked only when type of other does not
170  support multiplication with FormalSumContainerInterface
171  """
172  raise NotImplementedError("method '__rmul__' should be overridden")
173
174  def iterterms(self):
175  """
176  iterator for (degree, coefficient) pairs.
177  """
178  raise NotImplementedError("method 'iterterms' must be overridden")
179
180  def itercoefficients(self):
181  """
182  iterator for coefficients.
183  """
184  raise NotImplementedError("method 'itercoefficients' must be overridden")
185
186  def iterbases(self):
187  """
188  iterator for degrees.
189  """
190  raise NotImplementedError("method 'iterbases' must be overridden")
191
192  def terms(self):
193  """
194  Return a list of terms as (base, coefficient) pairs.
195  """
196  return list(self.iterterms())
197
198  def coefficients(self):
199  """
200  Return a list of all coefficients.
201  """
202  return list(self.itercoefficients())
203
204  def bases(self):
205  """
206  Return a list of all bases.
207  """
208  return list(self.iterbases())
209
210  def terms_map(self, func):
211  """
212  Create a new formal sum container by applying func to each
213  term. func must be a function taking 2 arguments.
214  """
215  terms = []
216  for t in self:
217  b, c = func(*t)
218  if c:
219  terms.append((b, c))
220  return self.construct_with_default(terms)
221
222  def coefficients_map(self, func):
223  """
224  Create a new formal sum container by applying func to each
225  coefficient.
226  """
227  return self.terms_map(lambda x, y: (x, func(y)))
228
229  def bases_map(self, func):
230  """
231  Create a new formal sum container by applying func to each
232  base.
233  """
234  return self.terms_map(lambda x, y: (func(x), y))
235
236  def construct_with_default(self, maindata):
237  """
238  Create a new formal sum container of the same class with self,
239  with given only the maindata and use copy of self's data if
240  necessary.
241  """
242  # Do not extend the signature of this method.
243  raise NotImplementedError("method 'construct_with_default' must be overridden")
244
245
247  """
248  formalsum implementation based on dict.
249  """
250  def __init__(self, args, defaultvalue=None):
251  """
252  DictFormalSum(args)
253
254  args can be any dict initial values.
255  It makes a mapping from bases to coefficients.
256
257  The optional argument defaultvalue is the default value for
258  __getitem__, i.e., if there is no term with the specified
259  base, a look up attempt returns the defaultvalue.
260  """
261  self._data = dict(args)
262  self._defaultvalue = defaultvalue
263
264  def __mul__(self, other):
265  """
266  self * other
267
268  Only scalar multiplication is defined.
269  """
270  return self.scalar_mul(other)
271
272  def scalar_mul(self, scale):
273  """
274  scalar multiplication.
275
276  self * scale
277  """
278  return self.coefficients_map(lambda c: c * scale)
279
280  def __rmul__(self, other):
281  """
282  other * self
283
284  This method is invoked only when type of other does not
285  support multiplication with FormalSumContainerInterface.
286  """
287  return self.rscalar_mul(other)
288
289  def rscalar_mul(self, scale):
290  """
291  r-scalar multiplication (r- means as of r-methods of python
292  special methods, where self is the right operand.)
293
294  scale * self
295  """
296  return self.coefficients_map(lambda c: scale * c)
297
298  def __neg__(self):
299  """
300  -self
301  """
302  return self.construct_with_default([(b, -c) for (b, c) in self])
303
304  def __pos__(self):
305  """
306  +self
307  """
308  return self.construct_with_default(self._data)
309
310  def __eq__(self, other):
311  """
312  self == other
313  """
314  if self is other:
315  return True
316  if not isinstance(other, DictFormalSum):
317  return FormalSumContainerInterface.__eq__(self, other)
318  if self._data == other._data:
319  return True
320  return False
321
322  def __hash__(self):
323  val = sum([hash(ele) for ele in self._data])
324  return val
325
326  def __getitem__(self, base):
327  """
328  self[base]
329
330  no KeyError will be raised. Insteads, it returns defaultvalue
331  specified on time of initialization.
332  """
333  return self._data.get(base, self._defaultvalue)
334
335  def iterterms(self):
336  """
337  iterator for (base, coefficient) pairs.
338  """
339  return self._data.iteritems()
340
341  def itercoefficients(self):
342  """
343  iterator for coefficients.
344  """
345  return self._data.itervalues()
346
347  def iterbases(self):
348  """
349  iterator for bases.
350  """
351  return self._data.iterkeys()
352
353  def __len__(self):
354  """
355  len(self)
356
357  Return the number of terms.
358  """
359  return len(self._data)
360
361  def __repr__(self): # for debug
362  return "%s(%s)" % (self.__class__.__name__, repr(self._data))
363
364  def construct_with_default(self, maindata):
365  """
366  Create a new formal sum container of the same class with self,
367  with given only the maindata and use copy of self's data if
368  necessary.
369  """
370  return self.__class__(maindata, defaultvalue=self._defaultvalue)
371
372
374  """
375  formalsum implementation based on List.
376  """
377  def __init__(self, args, defaultvalue=None):
378  """
379  ListFormalSum(args)
380
381  args can be sequence of tuples of (base, coefficient) pair.
382  It makes a mapping from bases to coefficients.
383  """
384  self._data = list(args)
385  self._defaultvalue = defaultvalue
386
387  def __mul__(self, other):
388  """
389  self * other
390
391  Only scalar multiplication is defined.
392  """
393  return self.scalar_mul(other)
394
395  def scalar_mul(self, scale):
396  """
397  scalar multiplication.
398
399  sum * scale
400  """
401  return self.coefficients_map(lambda c: c * scale)
402
403  def __rmul__(self, other):
404  """
405  other * self
406
407  This method is invoked only when type of other does not
408  support multiplication with FormalSum.
409  """
410  return self.rscalar_mul(other)
411
412  def rscalar_mul(self, scale):
413  """
414  scalar multiplication.
415
416  scale * sum
417  """
418  return self.coefficients_map(lambda c: scale * c)
419
420  def __neg__(self):
421  """
422  -self
423  """
424  return self.construct_with_default([(b, -c) for (b, c) in self])
425
426  def __pos__(self):
427  """
428  +self
429  """
430  return self.construct_with_default(self._data)
431
432  def __eq__(self, other):
433  """
434  self == other
435  """
436  if self is other:
437  return True
438  if not isinstance(other, ListFormalSum):
439  return FormalSumContainerInterface.__eq__(self, other)
440  if set(self._data) == set(other._data):
441  return True
442  return False
443
444  def __hash__(self):
445  val = sum([hash(ele) for ele in set(self._data)])
446  return val
447
448  def __getitem__(self, base):
449  """
450  self[base]
451
452  no KeyError will be raised. Insteads, it returns defaultvalue
453  specified on time of initialization.
454  """
455  for b, c in self:
456  if b == base:
457  return c
458  return self._defaultvalue
459
460  def iterterms(self):
461  """
462  iterator for (base, coefficient) pairs.
463  """
464  return iter(self._data)
465
466  def itercoefficients(self):
467  """
468  iterator for coefficients.
469  """
470  for b, c in self._data:
471  yield c
472
473  def iterbases(self):
474  """
475  iterator for bases.
476  """
477  for b, c in self._data:
478  yield b
479
480  def __len__(self):
481  """
482  len(self)
483
484  Return the number of terms.
485  """
486  return len(self._data)
487
488  def __repr__(self): # for debug
489  return "%s(%s)" % (self.__class__.__name__, repr(self._data))
490
491  def construct_with_default(self, maindata):
492  """
493  Create a new formal sum container of the same class with self,
494  with given only the maindata and use copy of self's data if
495  necessary.
496  """
497  return self.__class__(maindata, defaultvalue=self._defaultvalue)
nzmath.poly.formalsum.DictFormalSum.itercoefficients
def itercoefficients(self)
Definition: formalsum.py:341
nzmath.poly.formalsum.FormalSumContainerInterface.__mul__
def __mul__(self, other)
Definition: formalsum.py:157
nzmath.poly.formalsum.ListFormalSum._data
_data
Definition: formalsum.py:384
nzmath.poly.formalsum.DictFormalSum.__len__
def __len__(self)
Definition: formalsum.py:353
nzmath.poly.formalsum.DictFormalSum.__getitem__
def __getitem__(self, base)
Definition: formalsum.py:326
nzmath.poly.formalsum.FormalSumContainerInterface.bases_map
def bases_map(self, func)
Definition: formalsum.py:229
nzmath.poly.formalsum.ListFormalSum.__neg__
def __neg__(self)
Definition: formalsum.py:420
nzmath.poly.formalsum.ListFormalSum.itercoefficients
def itercoefficients(self)
Definition: formalsum.py:466
nzmath.poly.formalsum.FormalSumContainerInterface.bases
def bases(self)
Definition: formalsum.py:204
nzmath.poly.formalsum.DictFormalSum._data
_data
Definition: formalsum.py:261
nzmath.poly.formalsum.DictFormalSum.__init__
def __init__(self, args, defaultvalue=None)
Definition: formalsum.py:250
nzmath.poly.formalsum.ListFormalSum.construct_with_default
def construct_with_default(self, maindata)
Definition: formalsum.py:491
nzmath.poly.formalsum.DictFormalSum.__rmul__
def __rmul__(self, other)
Definition: formalsum.py:280
nzmath.poly.formalsum.FormalSumContainerInterface.__ne__
def __ne__(self, other)
Definition: formalsum.py:96
nzmath.poly.formalsum.ListFormalSum.iterbases
def iterbases(self)
Definition: formalsum.py:473
nzmath.poly.formalsum.DictFormalSum.iterbases
def iterbases(self)
Definition: formalsum.py:347
nzmath.poly.formalsum.FormalSumContainerInterface.__hash__
def __hash__(self)
Definition: formalsum.py:92
nzmath.poly.formalsum.FormalSumContainerInterface.__iter__
def __iter__(self)
Definition: formalsum.py:44
nzmath.poly.formalsum.FormalSumContainerInterface.terms
def terms(self)
Definition: formalsum.py:192
nzmath.poly.formalsum.ListFormalSum.__pos__
def __pos__(self)
Definition: formalsum.py:426
nzmath.poly.formalsum.ListFormalSum.__mul__
def __mul__(self, other)
Definition: formalsum.py:387
nzmath.poly.formalsum.DictFormalSum._defaultvalue
_defaultvalue
Definition: formalsum.py:262
nzmath.poly.formalsum.ListFormalSum.__rmul__
def __rmul__(self, other)
Definition: formalsum.py:403
nzmath.poly.formalsum.DictFormalSum.__repr__
def __repr__(self)
Definition: formalsum.py:361
nzmath.poly.formalsum.ListFormalSum.__eq__
def __eq__(self, other)
Definition: formalsum.py:432
nzmath.poly.formalsum.ListFormalSum.__len__
def __len__(self)
Definition: formalsum.py:480
nzmath.poly.formalsum.DictFormalSum.__mul__
def __mul__(self, other)
Definition: formalsum.py:264
nzmath.poly.formalsum.ListFormalSum.rscalar_mul
def rscalar_mul(self, scale)
Definition: formalsum.py:412
nzmath.poly.formalsum.FormalSumContainerInterface.terms_map
def terms_map(self, func)
Definition: formalsum.py:210
nzmath.poly.formalsum.FormalSumContainerInterface.coefficients_map
def coefficients_map(self, func)
Definition: formalsum.py:222
nzmath.poly.formalsum.ListFormalSum.iterterms
def iterterms(self)
Definition: formalsum.py:460
nzmath.poly.formalsum.ListFormalSum.__getitem__
def __getitem__(self, base)
Definition: formalsum.py:448
nzmath.poly.formalsum.FormalSumContainerInterface.__sub__
def __sub__(self, other)
Definition: formalsum.py:133
nzmath.poly.formalsum.FormalSumContainerInterface.__len__
def __len__(self)
Definition: formalsum.py:66
nzmath.poly.formalsum.ListFormalSum.__init__
def __init__(self, args, defaultvalue=None)
Definition: formalsum.py:377
nzmath.poly.formalsum.FormalSumContainerInterface.iterterms
def iterterms(self)
Definition: formalsum.py:174
nzmath.poly.formalsum.FormalSumContainerInterface.itercoefficients
def itercoefficients(self)
Definition: formalsum.py:180
nzmath.compatibility
Definition: compatibility.py:1
nzmath.poly.formalsum.FormalSumContainerInterface.construct_with_default
def construct_with_default(self, maindata)
Definition: formalsum.py:236
nzmath.poly.formalsum.ListFormalSum._defaultvalue
_defaultvalue
Definition: formalsum.py:385
nzmath.poly.formalsum.FormalSumContainerInterface.coefficients
def coefficients(self)
Definition: formalsum.py:198
nzmath.poly.formalsum.DictFormalSum.__eq__
def __eq__(self, other)
Definition: formalsum.py:310
nzmath.poly.formalsum.FormalSumContainerInterface.__eq__
def __eq__(self, other)
Definition: formalsum.py:72
nzmath.poly.formalsum.FormalSumContainerInterface.__getitem__
def __getitem__(self, base)
Definition: formalsum.py:51
nzmath.poly.formalsum.DictFormalSum.construct_with_default
def construct_with_default(self, maindata)
Definition: formalsum.py:364
nzmath.poly.formalsum.DictFormalSum.__pos__
def __pos__(self)
Definition: formalsum.py:304
nzmath.poly.formalsum.ListFormalSum.scalar_mul
def scalar_mul(self, scale)
Definition: formalsum.py:395
nzmath.poly.formalsum.DictFormalSum.rscalar_mul
def rscalar_mul(self, scale)
Definition: formalsum.py:289
nzmath.poly.formalsum.DictFormalSum.iterterms
def iterterms(self)
Definition: formalsum.py:335
nzmath.poly.formalsum.FormalSumContainerInterface.__rmul__
def __rmul__(self, other)
Definition: formalsum.py:165
nzmath.poly.formalsum.ListFormalSum.__hash__
def __hash__(self)
Definition: formalsum.py:444
nzmath.poly.formalsum.FormalSumContainerInterface.__neg__
def __neg__(self)
Definition: formalsum.py:145
nzmath.poly.formalsum.FormalSumContainerInterface.__pos__
def __pos__(self)
Definition: formalsum.py:151
nzmath.poly.formalsum.DictFormalSum.scalar_mul
def scalar_mul(self, scale)
Definition: formalsum.py:272
Definition: formalsum.py:121
nzmath.poly.formalsum.DictFormalSum.__neg__
def __neg__(self)
Definition: formalsum.py:298
nzmath.poly.formalsum.ListFormalSum.__repr__
def __repr__(self)
Definition: formalsum.py:488
nzmath.poly.formalsum.FormalSumContainerInterface.__nonzero__
def __nonzero__(self)
Definition: formalsum.py:102
nzmath.poly.formalsum.FormalSumContainerInterface.iterbases
def iterbases(self)
Definition: formalsum.py:186
nzmath.poly.formalsum.FormalSumContainerInterface.__contains__
def __contains__(self, base)
Definition: formalsum.py:58
nzmath.poly.formalsum.DictFormalSum.__hash__
def __hash__(self)
Definition: formalsum.py:322