## "Fossies" - the Fresh Open Source Software Archive

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

```    1 from __future__ import division
2 import logging
3 import nzmath.gcd as gcd
4 import nzmath.rational as rational
5 import nzmath.ring as ring
6 import nzmath.prime as prime
7
8
9 _log = logging.getLogger('nzmath.intresidue')
10
11
12 class IntegerResidueClass(ring.CommutativeRingElement):
13     """
14     A class for integer residue class.
15     """
16     def __init__(self, representative, modulus):
17         ring.CommutativeRingElement.__init__(self)
18         if modulus == 0:
19             raise ValueError("modulus can not be zero")
20         elif modulus < 0:
21             modulus = -modulus
22         self.m = modulus
23
24         if isinstance(representative, (int, long)):
25             self.n = representative % self.m
26         elif all(hasattr(representative, attr) for attr in ("m", "n")):
27             assert representative.m == modulus
28             self.n = representative.n
29         elif isinstance(representative, rational.Rational):
30             t = IntegerResidueClass(representative.denominator, self.m).inverse().getResidue()
31             self.n = representative.numerator * t % self.m
32         else:
33             raise NotImplementedError("%s is not made from %s." % (self.__class__.__name__, repr(representative),))
34
35     def __repr__(self):
36         return "IntegerResidueClass(%d, %d)" % (self.n, self.m)
37
38     def __mul__(self, other):
39         if isinstance(other, IntegerResidueClass):
40             if self.m == other.m:
41                 return self.__class__(self.n * other.n, self.m)
42             if self.m % other.m == 0:
43                 return IntegerResidueClass(self.n * other.n, other.m)
44             elif other.m % self.m == 0:
45                 return IntegerResidueClass(self.n * other.n, self.m)
46             else:
47                 raise ValueError("incompatible modulus: %d and %d" % (self.m, other.m))
48         try:
49             return self.mul_module_action(other)
50         except TypeError, e:
51             #trial may fail with TypeError.
52             #_log.debug("no action for %s * %s" % (str(self), str(other)))
53             pass
54         except AttributeError, e:
55             #trial may fail with AttributeError because other may lack ring.
56             #_log.debug("no action for %s * %s" % (str(self), str(other)))
57             pass
58         except RuntimeError, e:
59             # maximum recursion depth may exceed
60             #_log.debug("recursion limit for %s * %s" % (str(self), str(other)))
61             pass
62         return NotImplemented
63
64     def __rmul__(self, other):
65         try:
66             return self.mul_module_action(other)
67         except TypeError, e:
68             #trial may fail with TypeError.
69             #_log.debug("no action for %s * %s" % (str(other), str(self)))
70             pass
71         except AttributeError, e:
72             #trial may fail with AttributeError because other may lack ring.
73             #_log.debug("no action for %s * %s" % (str(other), str(self)))
74             pass
75         except RuntimeError, e:
76             # maximum recursion depth may exceed
77             #_log.debug("recursion limit for %s * %s" % (str(other), str(self)))
78             pass
79         return NotImplemented
80
81     def __div__(self, other):
82         try:
83             return self * other.inverse()
84         except AttributeError:
85             pass
86         try:
87             return self * self.__class__(other, self.m).inverse()
88         except (ValueError, NotImplementedError):
89             return NotImplemented
90
91     __floordiv__ = __truediv__ = __div__
92
93     def __mod__(self, other):
94         """
95         Return zero if division by other is allowed
96         """
97         return self - (self // other) * other
98
99     def __divmod__(self, other):
100         return (self // other, self % other)
101
102     def __rdiv__(self, other):
103         if not other:
104             return self.__class__(0, self.m)
105         else:
106             return NotImplemented
107
109         if isinstance(other, IntegerResidueClass):
110             if self.m == other.m:
111                 return self.__class__(self.n + other.n, self.m)
112             if self.m % other.m == 0:
113                 return IntegerResidueClass(self.n + other.n, other.m)
114             elif other.m % self.m == 0:
115                 return IntegerResidueClass(self.n + other.n, self.m)
116             else:
117                 raise ValueError("incompatible modulus: %d and %d" % (self.m, other.m))
118         try:
119             return self.__class__(self.n + other, self.m)
120         except:
121             return NotImplemented
122
124
125     def __sub__(self, other):
126         if isinstance(other, IntegerResidueClass):
127             if self.m == other.m:
128                 return self.__class__(self.n - other.n, self.m)
129             if self.m % other.m == 0:
130                 return IntegerResidueClass(self.n - other.n, other.m)
131             elif other.m % self.m == 0:
132                 return IntegerResidueClass(self.n - other.n, self.m)
133             else:
134                 raise ValueError("incompatible modulus: %d and %d" % (self.m, other.m))
135         try:
136             return self.__class__(self.n - other, self.m)
137         except:
138             return NotImplemented
139
140     def __rsub__(self, other):
141         try:
142             return self.__class__(other - self.n, self.m)
143         except:
144             return NotImplemented
145
146     def __pow__(self, other):
147         if other < 0:
148             inverse = self.inverse()
149             return self.__class__(pow(inverse.n, -other, self.m), self.m)
150         elif other == 0:
151             return self.__class__(1, self.m)
152         else:
153             return self.__class__(pow(self.n, other, self.m), self.m)
154
155     def __neg__(self):
156         return self.__class__(-self.n, self.m)
157
158     def __pos__(self):
159         return self.__class__(+self.n, self.m)
160
161     def __nonzero__(self):
162         return bool(self.n)
163
164     def __eq__(self, other):
165         if not other and self.n == 0:
166             return True
167         if isinstance(other, IntegerResidueClass):
168             if other.m == self.m and other.n == self.n:
169                 return True
170             else:
171                 return False
172         return NotImplemented
173
174     def __ne__(self, other):
175         return not (self == other)
176
177     def __hash__(self):
178         """
179         hash so that if a == b then hash(a) == hash(b).
180         """
181         return self.n & (2**32 - 1)
182
183     def inverse(self):
184         t = gcd.extgcd(self.n, self.m)
185         if t[2] != 1:
186             raise ZeroDivisionError("No inverse of %s." % self)
187         return self.__class__(t[0], self.m)
188
189     def getModulus(self):
190         return self.m
191
192     def getResidue(self):
193         return self.n
194
195     def minimumNonNegative(self):
196         """
197         Return the smallest non-negative representative element of the
198         residue class.
199         """
200         return rational.Integer(self.n % self.m)
201
202     toInteger = minimumNonNegative
203
204     def minimumAbsolute(self):
205         """
206         Return the minimum absolute representative integer of the
207         residue class.
208         """
209         result = self.n % self.m
210         if result > (self.m >> 1):
211             result -= self.m
212         return rational.Integer(result)
213
214     def getRing(self):
215         return IntegerResidueClassRing.getInstance(self.m)
216
217
218 class IntegerResidueClassRing(ring.CommutativeRing):
219     """
220     IntegerResidueClassRing is also known as Z/mZ.
221     """
222
223     _instances = {}
224
225     def __init__(self, modulus):
226         """
227         The argument modulus m specifies an ideal mZ.
228         """
229         ring.CommutativeRing.__init__(self)
230         self.m = modulus
231         self.registerModuleAction(rational.theIntegerRing, _mul_with_int)
232         # mathematically Q_m = Q \ {r/s; gcd(r, s) == 1, gcd(s, m) > 1}
233         # is more appropriate.
234         self.registerModuleAction(rational.theRationalField, _mul_with_rat)
235
236     def __repr__(self):
237         return "IntegerResidueClassRing(%d)" % self.m
238
239     def __str__(self):
240         return "Z/%dZ" % self.m
241
242     def __hash__(self):
243         return self.m & 0xFFFFFFFF
244
245     def card(self):
246         """
247         Return the cardinality of the ring.
248         """
249         return self.m
250
251     @classmethod
252     def getInstance(cls, modulus):
253         """
254         getInstance returns an instance of the class of specified
255         modulus.
256         """
257
258         if modulus not in cls._instances:
259             anInstance = IntegerResidueClassRing(modulus)
260             cls._instances[modulus] = anInstance
261         return cls._instances[modulus]
262
263     def createElement(self, seed):
264         if isinstance(seed, IntegerResidueClass) and seed.m % self.m == 0:
265             return IntegerResidueClass(seed.n, self.m)
266         try:
267             return IntegerResidueClass(seed, self.m)
268         except:
269             raise ValueError("%s can not be converted to an IntegerResidueClass object." % seed)
270
271     def getCharacteristic(self):
272         """
273         The characteristic of Z/mZ is m.
274         """
275         return self.m
276
277     def __contains__(self, elem):
278         if isinstance(elem, IntegerResidueClass) and \
279            elem.getModulus() == self.m:
280             return True
281         return False
282
283     def isfield(self):
284         """
285         isfield returns True if the modulus is prime, False if not.
286         Since a finite domain is a field, other ring property tests
287         are merely aliases of isfield.
288         """
289         if None == self.properties.isfield():
290             if prime.primeq(self.m):
291                 self.properties.setIsfield(True)
292             else:
293                 self.properties.setIsdomain(False)
294         return self.properties.isfield()
295
296     isdomain = isfield
297     isnoetherian = isfield
298     isufd = isfield
299     ispid = isfield
300     iseuclidean = isfield
301
302     def __eq__(self, other):
303         if isinstance(other, IntegerResidueClassRing) and self.m == other.m:
304             return True
305         return False
306
307     def __ne__(self, other):
308         return not (self == other)
309
310     def issubring(self, other):
311         if self == other:
312             return True
313         else:
314             return False
315
316     def issuperring(self, other):
317         if self == other:
318             return True
319         else:
320             return False
321
322     def _getOne(self):
323         "getter for one"
324         if self._one is None:
325             self._one = IntegerResidueClass(1, self.m)
326         return self._one
327
328     one = property(_getOne, None, None, "multiplicative unit.")
329
330     def _getZero(self):
331         "getter for zero"
332         if self._zero is None:
333             self._zero = IntegerResidueClass(0, self.m)
334         return self._zero
335
336     zero = property(_getZero, None, None, "additive unit.")
337
338
339 def _mul_with_int(integer, residue):
340     """
341     Return k * IntegerResidueClass(n, m)
342     """
343     return residue.__class__(integer * residue.n, residue.m)
344
345 def _mul_with_rat(rat, residue):
346     """
347     Return Rational(a, b) * IntegerResidueClass(n, p)
348     """
349     return residue.__class__(rat * residue.n, residue.m)
```