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

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

```    1 """
2 base classes for rings.
3 """
4
5 from __future__ import division
6
7
8 class Ring (object):
9     """
10     Ring is an abstract class which expresses that
11     the derived classes are (in mathematical meaning) rings.
12
13     Definition of ring is as follows:
14       Ring is a structure with addition and multiplication.  It is an
15       abelian group with addition, and a monoid with multiplication.
16       The multiplication obeys the distributive law.
17     """
18
19     def __init__(self):
20         """
21         Initialize _one and _zero for later use for properties 'one'
22         and 'zero'.
23         """
24         # This class is abstract and cannot be instantiated.
25         if type(self) is Ring:
26             raise NotImplementedError("class Ring is abstract")
27         self._one = None
28         self._zero = None
29
30     def createElement(self, seed):
31         """
32         createElement returns an element of the ring with seed.
33         """
34         raise NotImplementedError("derived class should override")
35
36     def getCharacteristic(self):
37         """
38         Return the characteristic of the ring.
39
40         The Characteristic of a ring is the smallest positive integer
41         n s.t. n * a = 0 for any element a of the ring, or 0 if there
42         is no such natural number.
43         """
44         raise NotImplementedError("derived class should override")
45
46     def issubring(self, other):
47         """
48         Report whether another ring contains the ring as a subring.
49         """
50         raise NotImplementedError("derived class should override")
51
52     def issuperring(self, other):
53         """
54         Report whether the ring is a superring of another ring.
55         """
56         raise NotImplementedError("derived class should override")
57
58     def getCommonSuperring(self, other):
59         """
60         Return common super ring of self and another ring.
61         """
62         if self.issubring(other):
63             return other
64         elif self.issuperring(other):
65             return self
66         try:
67             return other.getCommonSuperring(self)
68         except RuntimeError:
69             # reached recursion limit by calling on each other
70             raise NotImplementedError("no common super ring")
71
72     def __eq__(self, other):
73         """
74         Equality test.
75         """
76         raise NotImplementedError("derived class should override")
77
78     def __hash__(self):
79         raise NotImplementedError("derived class should override")
80
81     def __ne__(self, other):
82         """
83         Inequality test.
84         """
85         return not self.__eq__(other)
86
87
88 class CommutativeRing (Ring):
89     """
90     CommutativeRing is an abstract subclass of Ring
91     whose multiplication is commutative.
92     """
93
94     def __init__(self):
95         """
96         Initialize 'properties' attribute by an object of
97         CommutativeRingProperties.
98         """
99         # This class is abstract and cannot be instantiated.
100         if type(self) is CommutativeRing:
101             raise NotImplementedError("class CommutativeRing is abstract")
102         Ring.__init__(self)
103         self.properties = CommutativeRingProperties()
104         self._actions = {}
105         self._actions_order = []
106
107     def getQuotientField(self):
108         """
109         getQuotientField returns the quotient field of the ring
110         if available, otherwise raises exception.
111         """
112         raise NotImplementedError
113
114     def isdomain(self):
115         """
116         isdomain returns True if the ring is actually a domain,
117         False if not, or None if uncertain.
118         """
119         return self.properties.isdomain()
120
121     def isnoetherian(self):
122         """
123         isnoetherian returns True if the ring is actually a Noetherian
124         domain, False if not, or None if uncertain.
125         """
126         return self.properties.isnoetherian()
127
128     def isufd(self):
129         """
130         isufd returns True if the ring is actually a unique
131         factorization domain, False if not, or None if uncertain.
132         """
133         return self.properties.isufd()
134
135     def ispid(self):
136         """
137         ispid returns True if the ring is actually a principal
138         ideal domain, False if not, or None if uncertain.
139         """
140         return self.properties.ispid()
141
142     def iseuclidean(self):
143         """
144         iseuclidean returns True if the ring is actually a Euclidean
145         domain, False if not, or None if uncertain.
146         """
147         return self.properties.iseuclidean()
148
149     def isfield(self):
150         """
151         isfield returns True if the ring is actually a field,
152         False if not, or None if uncertain.
153         """
154         return self.properties.isfield()
155
156     def registerModuleAction(self, action_ring, action):
157         """
158         Register a ring 'action_ring', which act on the ring through
159         'action' so the ring be an 'action_ring' module.
160         """
161         self._actions[action_ring] = action
162         for i in range(len(self._actions_order) - 1, -1, -1):
163             if self._actions_order[i].issubring(action_ring):
164                 self._actions_order.insert(i + 1, action_ring)
165                 break
166         else:
167             self._actions_order.insert(0, action_ring)
168
169     def hasaction(self, action_ring):
170         """
171         Return True if 'action_ring' is registered to provide action.
172         """
173         if action_ring in self._actions:
174             return True
175         for action_superring in self._actions_order:
176             if action_ring.issubring(action_superring):
177                 return True
178         return False
179
180     def getaction(self, action_ring):
181         """
182         Return the registered action for 'action_ring'.
183         """
184         for action_superring in self._actions_order:
185             if action_ring.issubring(action_superring):
186                 return self._actions[action_superring]
187         raise KeyError("no action is defined")
188
189
190 class Field (CommutativeRing):
191     """
192     Field is an abstract class which expresses that
193     the derived classes are (in mathematical meaning) fields.
194     """
195
196     def __init__(self):
197         """
198         Set field flag True of 'properties' attribute.
199         """
200         # This class is abstract and cannot be instantiated.
201         if type(self) is Field:
202             raise NotImplementedError
203         CommutativeRing.__init__(self)
204         self.properties.setIsfield(True)
205
206     def createElement(self, *args):
207         """
208         createElement returns an element of the field.
209         """
210         raise NotImplementedError
211
212     def isfield(self):
213         """
214         Field overrides isfield of CommutativeRing.
215         """
216         return True
217
218     def gcd(self, a, b):
219         """
220         A field is trivially a ufd and shuold provide gcd.
221         """
222         if not a and not b:
223             return self.zero
224         return self.one
225
226     def getQuotientField(self):
227         """
228         getQuotientField returns the quotient field of the field.
229         It is, of course, itself.
230         """
231         return self
232
233
234 class QuotientField (Field):
235     """
236     QuotientField is a class of quotient field.
237     """
238
239     def __init__(self, domain):
240         """
241         Create quotient field from given domain.
242         Initialize 'basedomain' attribute by the given 'domain'.
243         """
244         # This class is abstract and cannot be instantiated.
245         if type(self) is QuotientField:
246             raise NotImplementedError("QuotientField is an abstract class")
247         Field.__init__(self)
248         self.basedomain = domain
249
250         def baseaction(baseelement, quotient):
251             return quotient.__class__(baseelement * quotient.numerator, quotient.denominator)
252
253         self.registerModuleAction(self.basedomain, baseaction)
254
255
256 class RingElement (object):
257     """
258     RingElement is an abstract class for elements of rings.
259     """
260
261     def __init__(self, *args, **kwd):
262         """
263         This class is abstract and cannot be instantiated.
264         """
265         if type(self) is RingElement:
266             raise NotImplementedError("RingElement is an abstract class.")
267
268     def getRing(self):
269         """
270         getRing returns an object of a subclass of Ring,
271         to which the element belongs.
272         """
273         raise NotImplementedError
274
275     def __eq__(self, other):
276         """
277         Equality test.
278         """
279         raise NotImplementedError
280
281     def __hash__(self):
282         raise NotImplementedError
283
284     def __ne__(self, other):
285         """
286         Inequality test.
287         """
288         return not (self == other)
289
290
291 class CommutativeRingElement (RingElement):
292     """
293     CommutativeRingElement is an abstract class for elements of
294     commutative rings.
295     """
296
297     def __init__(self):
298         """
299         This class is abstract and cannot be instantiated.
300         """
301         if type(self) is CommutativeRingElement:
302             raise NotImplementedError("CommutativeRingElement is an abstract class.")
303         RingElement.__init__(self)
304
305     def mul_module_action(self, other):
306         """
307         Return the result of a module action.
308         other must be in one of the action rings of self's ring.
309         """
310         try:
311             self_ring = self.getRing()
312             other_ring = getRing(other)
313             if self_ring.hasaction(other_ring):
314                 return self_ring.getaction(other_ring)(other, self)
315         except RuntimeError, e:
316             #print "mul_module_action", e
317             raise
318         raise TypeError("no module action with %s" % str(other_ring))
319
320     def exact_division(self, other):
321         """
322         In UFD, if other divides self, return the quotient as a UFD
323         element.  The main difference with / is that / may return the
324         quotient as an element of quotient field.
325
326         Simple cases:
327         - in a euclidean domain, if remainder of euclidean division
328           is zero, the division // is exact.
329         - in a field, there's no difference with /.
330
331         If other doesn't divide self, raise ValueError.
332         """
333         if self.getRing().iseuclidean():
334             quotient, remainder = divmod(self, other)
335             if not remainder:
336                 return quotient
337             raise ValueError("division is not exact")
338         elif self.getRing().isfield():
339             return self / other
340         raise NotImplementedError("exact division is not defined")
341
342
343 class FieldElement (CommutativeRingElement):
344     """
345     FieldElement is an abstract class for elements of fields.
346     """
347     def __init__(self):
348         """
349         This class is abstract and cannot be instantiated.
350         """
351         if type(self) is FieldElement:
352             raise NotImplementedError("FieldElement is an abstract class.")
353         CommutativeRingElement.__init__(self)
354
355     def exact_division(self, other):
356         """
357         in a field, all divisions are exact (without remainder).
358         """
359         return self / other
360
361 class QuotientFieldElement (FieldElement):
362     """
363     QuotientFieldElement class is an abstract class to be used as a
364     super class of concrete quotient field element classes.
365     """
366
367     def __init__(self, numerator, denominator):
368         FieldElement.__init__(self)
369         self.numerator = numerator
370         if denominator == 0:
371             raise ZeroDivisionError
372         self.denominator = denominator
373
375         if hasattr(other, "numerator") and hasattr(other, "denominator"):
376             numerator = self.numerator*other.denominator + self.denominator*other.numerator
377             denominator = self.denominator*other.denominator
378             return self.__class__(numerator, denominator)
379         try:
380             return self + self.getRing().one.mul_module_action(other)
381         except TypeError:
382             return NotImplemented
383
385
386     def __sub__(self, other):
387         if hasattr(other, "numerator") and hasattr(other, "denominator"):
388             numerator = self.numerator*other.denominator - self.denominator*other.numerator
389             denominator = self.denominator*other.denominator
390             return self.__class__(numerator, denominator)
391         try:
392             return self - self.getRing().one.mul_module_action(other)
393         except TypeError:
394             return NotImplemented
395
396     def __rsub__(self, other):
397         if hasattr(other, "numerator") and hasattr(other, "denominator"):
398             numerator = self.denominator*other.numerator - self.numerator*other.denominator
399             denominator = self.denominator*other.denominator
400             return self.__class__(numerator, denominator)
401         try:
402             return self.getRing().one.mul_module_action(other) - self
403         except TypeError:
404             return NotImplemented
405
406     def __neg__(self):
407         return self.__class__(-self.numerator, self.denominator)
408
409     def __mul__(self, other):
410         if hasattr(other, "numerator") and hasattr(other, "denominator"):
411             numerator = self.numerator * other.numerator
412             denominator = self.denominator * other.denominator
413             return self.__class__(numerator, denominator)
414         try:
415             return self.mul_module_action(other)
416         except TypeError:
417             return NotImplemented
418
419     __rmul__ = __mul__
420
421     def __pow__(self, index):
422         return self.__class__(self.numerator ** index, self.denominator ** index)
423
424     def __truediv__(self, other):
425         if hasattr(other, "numerator") and hasattr(other, "denominator"):
426             numerator = self.numerator * other.denominator
427             denominator = self.denominator * other.numerator
428             return self.__class__(numerator, denominator)
429         try:
430             return self * self.getRing().one.mul_module_action(other).inverse()
431         except TypeError:
432             return NotImplemented
433
434     def __rtruediv__(self, other):
435         if hasattr(other, "numerator") and hasattr(other, "denominator"):
436             numerator =  other.numerator * self.denominator
437             denominator = other.denominator * self.numerator
438             return self.__class__(numerator, denominator)
439         try:
440             return self.getRing().one.mul_module_action(other) * self.inverse()
441         except TypeError:
442             return NotImplemented
443
444     __div__ = __truediv__
445
446     def inverse(self):
447         return self.__class__(self.denominator, self.numerator)
448
449     def __eq__(self, other):
450         if hasattr(other, "numerator") and hasattr(other, "denominator"):
451             return self.numerator*other.denominator == self.denominator*other.numerator
452         try:
453             return self == self.getRing().one.mul_module_action(other)
454         except TypeError:
455             return NotImplemented
456
457     def __hash__(self):
458         return hash(self.numerator * self.denominator)
459
460 class Ideal (object):
461     """
462     Ideal class is an abstract class to represent the finitely
463     generated ideals.  Because the finitely-generatedness is not a
464     restriction for Noetherian rings and in the most cases only
465     Noetherian rings are used, it is general enough.
466     """
467
468     def __init__(self, generators, aring):
469         """
470         Ideal(generators, ring) creates an ideal of the ring genarated
471         by the generators.  generators must be an element of the ring
472         or a list of elements of the ring.
473         """
474         if type(self) is Ideal:
475             raise NotImplementedError("class Ideal is abstract")
476         self.ring = aring
477         if not generators:
478             self.generators = [self.ring.zero]
479         elif generators in self.ring:
480             self.generators = [generators]
481         else:
482             self.generators = list(generators)
483
485         """
486         I + J <=> I.__add__(J)
487
488         where I+J = {i+j | i in I and j in J}
489         """
490         assert self.ring is other.ring
491         if self == other:
492             return self
493         return self.__class__(self.generators + other.generators, self.ring)
494
495     def __mul__(self, other):
496         """
497         I * J <=> I.__mul__(J)
498
499         where I*J = {sum of i*j | i in I and j in J}
500         """
501         assert self.ring is other.ring
502         generators = []
503         for i in self.generators:
504             for j in other.generators:
505                 generators.append(i * j)
506         return self.__class__(generators, self.ring)
507
508     def __eq__(self, other):
509         """
510         I == J <=> I.__eq__(J)
511         """
512         assert type(self) is type(other)
513         if self is other:
514             return True
515         if self.ring is not other.ring:
516             return False
517         return self.issubset(other) and self.issuperset(other)
518
519     def __hash__(self):
520         raise NotImplementedError
521
522     def __ne__(self, other):
523         """
524         I != J <=> I.__ne__(J)
525         """
526         return not self.__eq__(other)
527
528     def __contains__(self, element):
529         """
530         e in I  <=>  I.__contains__(e)
531
532         for e in the ring, to which the ideal I belongs.
533         """
534         raise NotImplementedError("should be overridden")
535
536     def issubset(self, other):
537         """
538         Report whether another ideal contains this ideal.
539         """
540         if self is other:
541             return True
542         raise NotImplementedError("should be overridden")
543
544     def issuperset(self, other):
545         """
546         Report whether this ideal contains another ideal.
547         """
548         if self is other:
549             return True
550         raise NotImplementedError("should be overridden")
551
552     def reduce(self, element):
553         """
554         Reduce an element with the ideal to simpler representative.
555         """
556         raise NotImplementedError("should be overridden")
557
558
559 class ResidueClassRing (CommutativeRing):
560     """
561     A residue class ring R/I,
562     where R is a commutative ring and I is its ideal.
563     """
564
565     def __init__(self, ring, ideal):
566         """
567         ResidueClassRing(ring, ideal) creates a resudue class ring.
568         The ring should be an instance of CommutativeRing, and ideal
569         must be an instance of Ideal, whose ring attribute points the
570         same ring with the given ring.
571         """
572         CommutativeRing.__init__(self)
573         self.ring = ring
574         self.ideal = ideal
575         if self.ring.isnoetherian():
576             self.properties.setIsnoetherian(True)
577
578     def __contains__(self, element):
579         if isinstance(element, ResidueClass) and element.ideal == self.ideal:
580             return True
581         return False
582
583     def __eq__(self, other):
584         if isinstance(other, ResidueClassRing):
585             return self.ideal == other.ideal
586         return False
587
588     def __hash__(self):
589         return hash(self.ideal)
590
591     # properties
592     def _getOne(self):
593         "getter for one"
594         if self._one is None:
595             seed = self.ring.one
596             if seed is not None:
597                 self._one = ResidueClass(seed, self.ideal)
598         return self._one
599
600     one = property(_getOne, None, None, "multiplicative unit.")
601
602     def _getZero(self):
603         "getter for zero"
604         if self._zero is None:
605             seed = self.ring.zero
606             if seed is not None:
607                 self._zero = ResidueClass(seed, self.ideal)
608         return self._zero
609
610     zero = property(_getZero, None, None, "additive unit.")
611
612
613 class ResidueClass (CommutativeRingElement):
614     """
615     Element of residue class ring x+I, where I is the modulus ideal
616     and x is a representative element.
617     """
618
619     def __init__(self, x, ideal):
620         CommutativeRingElement.__init__(self)
621         self.x = x
622         self.ideal = ideal
623
624     def __pos__(self):
625         return self.__class__(self.ideal.reduce(self.x ), self.ideal)
626
628         assert self.ideal == other.ideal
629         return self.__class__(self.ideal.reduce(self.x + other.x), self.ideal)
630
631     def __sub__(self, other):
632         assert self.ideal == other.ideal
633         return self.__class__(self.ideal.reduce(self.x - other.x), self.ideal)
634
635     def __mul__(self, other):
636         assert self.ideal == other.ideal
637         return self.__class__(self.ideal.reduce(self.x * other.x), self.ideal)
638
639     def __eq__(self, other):
640         if isinstance(other, ResidueClass):
641             if self.ideal == other.ideal:
642                 return (self.x - other.x) in self.ideal
643         return False
644
645     def __hash__(self):
646         raise NotImplementedError
647
648     def getRing(self):
649         """
650         Return a ResidueClassRing object.
651         This overrides the method inherited from CommutativeRingElement.
652         """
653         return ResidueClassRing(self.ideal.ring, self.ideal)
654
655
656 class CommutativeRingProperties (object):
657     """
658     boolean properties of ring.
659
660     Each property can have one of three values; True, False, or None.
661     Of cource True is true and False is false, and None means that the
662     property is not set neither directly nor indirectly.
663     """
664
665     def __init__(self):
666         self._isfield = None
667         self._iseuclidean = None
668         self._ispid = None
669         self._isufd = None
670         self._isnoetherian = None
671         self._isdomain = None
672
673     def isfield(self):
674         """
675         Return True/False according to the field flag value being set,
676         otherwise return None.
677         """
678         return self._isfield
679
680     def setIsfield(self, value):
681         """
682         Set True/False value to the field flag.
683         Propergation:
684           True -> euclidean
685         """
686         self._isfield = bool(value)
687         if self._isfield:
688             self.setIseuclidean(True)
689
690     def iseuclidean(self):
691         """
692         Return True/False according to the euclidean flag value being
693         set, otherwise return None.
694         """
695         return self._iseuclidean
696
697     def setIseuclidean(self, value):
698         """
699         Set True/False value to the euclidean flag.
700         Propergation:
701           True  -> pid
702           False -> field
703         """
704         self._iseuclidean = bool(value)
705         if self._iseuclidean:
706             self.setIspid(True)
707         else:
708             self.setIsfield(False)
709
710     def ispid(self):
711         """
712         Return True/False according to the pid flag value being set,
713         otherwise return None.
714         """
715         return self._ispid
716
717     def setIspid(self, value):
718         """
719         Set True/False value to the pid flag.
720         Propergation:
721           True  -> ufd, noetherian
722           False -> euclidean
723         """
724         self._ispid = bool(value)
725         if self._ispid:
726             self.setIsufd(True)
727             self.setIsnoetherian(True)
728         else:
729             self.setIseuclidean(False)
730
731     def isufd(self):
732         """
733         Return True/False according to the ufd flag value being set,
734         otherwise return None.
735         """
736         return self._isufd
737
738     def setIsufd(self, value):
739         """
740         Set True/False value to the ufd flag.
741         Propergation:
742           True  -> domain
743           False -> pid
744         """
745         self._isufd = bool(value)
746         if self._isufd:
747             self.setIsdomain(True)
748         else:
749             self.setIspid(False)
750
751     def isnoetherian(self):
752         """
753         Return True/False according to the noetherian flag value being
754         set, otherwise return None.
755         """
756         return self._isnoetherian
757
758     def setIsnoetherian(self, value):
759         """
760         Set True/False value to the noetherian flag.
761         Propergation:
762           True  -> domain
763           False -> pid
764         """
765         self._isnoetherian = bool(value)
766         if self._isnoetherian:
767             self.setIsdomain(True)
768         else:
769             self.setIspid(False)
770
771     def isdomain(self):
772         """
773         Return True/False according to the domain flag value being
774         set, otherwise return None.
775         """
776         return self._isdomain
777
778     def setIsdomain(self, value):
779         """
780         Set True/False value to the domain flag.
781         Propergation:
782           False  -> ufd, noetherian
783         """
784         self._isdomain = bool(value)
785         if not self._isdomain:
786             self.setIsufd(False)
787             self.setIsnoetherian(False)
788
789
790 def getRingInstance(obj):
791     """
792     Return a RingElement instance which eqauls 'obj'.
793
794     Mainly for python built-in objects such as int or float.
795     """
796     if isinstance(obj, RingElement):
797         return obj
798     elif isinstance(obj, (int, long)):
799         import nzmath.rational as rational
800         return rational.Integer(obj)
801     elif isinstance(obj, float):
802         import nzmath.real as real
803         return real.Real(obj)
804     elif isinstance(obj, complex):
805         import nzmath.imaginary as imaginary
806         return imaginary.Complex(obj)
807     return None
808
809 def getRing(obj):
810     """
811     Return a ring to which 'obj' belongs.
812
813     Mainly for python built-in objects such as int or float.
814     """
815     try:
816         # if obj has its getRing method, use it.
817         return obj.getRing()
818     except AttributeError:
819         if isinstance(obj, (int, long)):
820             import nzmath.rational as rational
821             return rational.theIntegerRing
822         if isinstance(obj, float):
823             import nzmath.real as real
824             return real.theRealField
825         if isinstance(obj, complex):
826             import nzmath.imaginary as imaginary
827             return imaginary.theComplexField
828     return None
829
830 def inverse(obj):
831     """
832     Return the inverse of 'obj'.  The inverse can be in the quotient
833     field, if the 'obj' is an element of non-field domain.
834
835     Mainly for python built-in objects such as int or float.
836     """
837     if hasattr(obj, "inverse"):
838         return obj.inverse()
839     # special cases
840     if isinstance(obj, (int, long)):
841         import nzmath.rational as rational
842         return rational.Rational(1, obj)
843     elif isinstance(obj, (float, complex)):
844         return 1 / obj
845     # final trial
846     try:
847         # if true division does not fail, it should return the inverse
848         return getRing(obj).one / obj
849     except TypeError:
850         raise NotImplementedError("no inversion method found")
851
852 def exact_division(self, other):
853     """
854     Return the division of 'self' by 'obj' if the division is exact.
855
856     Mainly for python built-in objects such as int or float.
857     """
858     return getRingInstance(self).exact_division(other)
```