"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 
  108     def __add__(self, other):
  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 
  123     __radd__ = __add__
  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)