"Fossies" - the Fresh Open Source Software Archive

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

    1 """
    2 rational module provides Rational, Integer, RationalField, and IntegerRing.
    3 """
    4 
    5 import nzmath.gcd as gcd
    6 import nzmath.ring as ring
    7 from nzmath.plugins import MATHMODULE as math, FLOATTYPE as Float
    8 
    9 
   10 class Rational (ring.QuotientFieldElement):
   11     """
   12     Rational is the class of rational numbers.
   13     """
   14 
   15     def __init__(self, numerator, denominator=1):
   16         """
   17         Create a rational from:
   18           * integers,
   19           * float, or
   20           * Rational.
   21         Other objects can be converted if they have toRational
   22         methods.  Otherwise raise TypeError.
   23         """
   24         if not denominator:
   25             raise ZeroDivisionError
   26         # numerator
   27         integer = (int, long)
   28         initDispatcher = {
   29             (Rational, Rational): Rational._init_by_Rational_Rational,
   30             (float, Rational): Rational._init_by_float_Rational,
   31             (integer, Rational): Rational._init_by_int_Rational,
   32             (Rational, float): Rational._init_by_Rational_float,
   33             (float, float): Rational._init_by_float_float,
   34             (integer, float): Rational._init_by_int_float,
   35             (Rational, integer): Rational._init_by_Rational_int,
   36             (float, integer): Rational._init_by_float_int,
   37             (integer, integer): Rational._init_by_int_int,
   38             }
   39         if not isinstance(numerator, (Rational, float, int, long)):
   40             if hasattr(numerator, "toRational"):
   41                 numerator = numerator.toRational()
   42             elif hasattr(numerator, "__pos__"):
   43                 numerator = +numerator
   44         if not isinstance(denominator, (Rational, float, int, long)):
   45             if hasattr(denominator, "toRational"):
   46                 denominator = denominator.toRational()
   47             elif hasattr(numerator, "__pos__"):
   48                 denominator = +denominator
   49         for (t1, t2) in initDispatcher:
   50             if isinstance(numerator, t1) and isinstance(denominator, t2):
   51                 initDispatcher[(t1, t2)](self, numerator, denominator)
   52                 break
   53         else:
   54             try:
   55                 cfe = continued_fraction_expansion(numerator / denominator, 50)
   56                 approx0 = Rational(cfe[0])
   57                 approx1 = Rational(cfe[1] * cfe[0] + 1, cfe[1])
   58                 for q in cfe[2:]:
   59                     approx0, approx1 = approx1, Rational(q * approx1.numerator + approx0.numerator, q * approx1.denominator + approx0.denominator)
   60                 self.numerator, self.denominator = approx1.numerator, approx1.denominator
   61                 return
   62             except Exception:
   63                 # maybe some type could raise strange error ...
   64                 pass
   65             raise TypeError("Rational cannot be created with %s(%s) and %s(%s)." % (numerator, numerator.__class__, denominator, denominator.__class__))
   66         self._reduce()
   67 
   68     def __add__(self, other):
   69         """
   70         self + other
   71 
   72         If other is a rational or an integer, the result will be a
   73         rational.  If other is a kind of float the result is an
   74         instance of other's type.  Otherwise, other would do the
   75         computation.
   76         """
   77         if isinstance(other, Rational):
   78             numerator = self.numerator*other.denominator + self.denominator*other.numerator
   79             denominator = self.denominator*other.denominator
   80             return +Rational(numerator, denominator)
   81         elif isIntegerObject(other):
   82             numerator = self.numerator + self.denominator*other
   83             denominator = self.denominator
   84             return +Rational(numerator, denominator)
   85         elif isinstance(other, Float):
   86             return self.toFloat() + other
   87         elif isinstance(other, float):
   88             return float(self) + other
   89         else:
   90             return NotImplemented
   91 
   92     def __sub__(self, other):
   93         """
   94         self - other
   95 
   96         If other is a rational or an integer, the result will be a
   97         rational.  If other is a kind of float the result is an
   98         instance of other's type.  Otherwise, other would do the
   99         computation.
  100         """
  101         if isinstance(other, Rational):
  102             numerator = self.numerator*other.denominator - self.denominator*other.numerator
  103             denominator = self.denominator*other.denominator
  104             return +Rational(numerator, denominator)
  105         elif isIntegerObject(other):
  106             numerator = self.numerator - self.denominator*other
  107             denominator = self.denominator
  108             return +Rational(numerator, denominator)
  109         elif isinstance(other, Float):
  110             return self.toFloat() - other
  111         elif isinstance(other, float):
  112             return float(self) - other
  113         else:
  114             return NotImplemented
  115 
  116     def __mul__(self, other):
  117         """
  118         self * other
  119 
  120         If other is a rational or an integer, the result will be a
  121         rational.  If other is a kind of float the result is an
  122         instance of other's type.  Otherwise, other would do the
  123         computation.
  124         """
  125         if isinstance(other, Rational):
  126             numerator = self.numerator*other.numerator
  127             denominator = self.denominator*other.denominator
  128             return +Rational(numerator, denominator)
  129         elif isIntegerObject(other):
  130             numerator = self.numerator*other
  131             denominator = self.denominator
  132             return +Rational(numerator, denominator)
  133         elif isinstance(other, Float):
  134             return self.toFloat() * other
  135         elif isinstance(other, float):
  136             return float(self) * other
  137         else:
  138             return NotImplemented
  139 
  140     def __truediv__(self, other):
  141         """
  142         self / other
  143         self // other
  144 
  145         If other is a rational or an integer, the result will be a
  146         rational.  If other is a kind of float the result is an
  147         instance of other's type.  Otherwise, other would do the
  148         computation.
  149         """
  150         if isinstance(other, Rational):
  151             numerator = self.numerator*other.denominator
  152             denominator = self.denominator*other.numerator
  153             return +Rational(numerator, denominator)
  154         elif isIntegerObject(other):
  155             q, r = divmod(self.numerator, other)
  156             if r == 0:
  157                 return Rational(q, self.denominator)
  158             numerator = self.numerator
  159             denominator = self.denominator*other
  160             return +Rational(numerator, denominator)
  161         elif isinstance(other, Float):
  162             return self.toFloat() / other
  163         elif isinstance(other, float):
  164             return float(self) / other
  165         else:
  166             return NotImplemented
  167 
  168     __div__ = __truediv__
  169     __floordiv__ = __truediv__
  170 
  171     def __radd__(self, other):
  172         """
  173         other + self
  174 
  175         If other is an integer, the result will be a rational.  If
  176         other is a kind of float the result is an instance of other's
  177         type.  Otherwise, other would do the computation.
  178         """
  179         if isIntegerObject(other):
  180             numerator = self.numerator + self.denominator*other
  181             denominator = self.denominator
  182             return +Rational(numerator, denominator)
  183         elif isinstance(other, Float):
  184             return other + self.toFloat()
  185         elif isinstance(other, float):
  186             return other + float(self)
  187         else:
  188             return NotImplemented
  189 
  190     def __rsub__(self, other):
  191         """
  192         other - self
  193 
  194         If other is an integer, the result will be a rational.  If
  195         other is a kind of float the result is an instance of other's
  196         type.  Otherwise, other would do the computation.
  197         """
  198         if isIntegerObject(other):
  199             numerator = self.denominator*other - self.numerator
  200             denominator = self.denominator
  201             return +Rational(numerator, denominator)
  202         elif isinstance(other, Float):
  203             return other - self.toFloat()
  204         elif isinstance(other, float):
  205             return other - float(self)
  206         else:
  207             return NotImplemented
  208 
  209     def __rmul__(self, other):
  210         """
  211         other * self
  212 
  213         If other is an integer, the result will be a rational.  If
  214         other is a kind of float the result is an instance of other's
  215         type.  Otherwise, other would do the computation.
  216         """
  217         if isIntegerObject(other):
  218             numerator = self.numerator*other
  219             denominator = self.denominator
  220             return +Rational(numerator, denominator)
  221         elif isinstance(other, Float):
  222             return other * self.toFloat()
  223         elif isinstance(other, float):
  224             return other * float(self)
  225         else:
  226             return NotImplemented
  227 
  228     def __rtruediv__(self, other):
  229         """
  230         other / self
  231         other // self
  232 
  233         If other is an integer, the result will be a rational.  If
  234         other is a kind of float the result is an instance of other's
  235         type.  Otherwise, other would do the computation.
  236         """
  237         if isIntegerObject(other):
  238             if other == 1:
  239                 return Rational(self.denominator, self.numerator)
  240             numerator = self.denominator*other
  241             denominator = self.numerator
  242             return +Rational(numerator, denominator)
  243         elif isinstance(other, Float):
  244             return other / self.toFloat()
  245         elif isinstance(other, float):
  246             return other / float(self)
  247         else:
  248             return NotImplemented
  249 
  250     __rdiv__ = __rtruediv__
  251     __rfloordiv__ = __rtruediv__
  252 
  253     def __pow__(self, index):
  254         assert isIntegerObject(index)
  255         if index > 0:
  256             return +Rational(self.numerator ** index, self.denominator ** index)
  257         elif index < 0:
  258             if index == -1:
  259                 return Rational(self.denominator, self.numerator)
  260             return +Rational(self.denominator ** (-index), self.numerator ** (-index))
  261         else:
  262             return Integer(1)
  263 
  264     def __lt__(self, other):
  265         return self.compare(other) < 0
  266 
  267     def __le__(self, other):
  268         return self.compare(other) <= 0
  269 
  270     def __eq__(self, other):
  271         if isIntegerObject(other):
  272             if self.denominator == 1:
  273                 return self.numerator == other
  274             elif self.numerator % self.denominator == 0:
  275                 return self.numerator // self.denominator == other
  276             else:
  277                 return False
  278         elif hasattr(other, "denominator") and hasattr(other, "numerator"):
  279             return self.compare(other) == 0
  280         else:
  281             return NotImplemented
  282 
  283     def __ne__(self, other):
  284         return self.compare(other) != 0
  285 
  286     def __gt__(self, other):
  287         return self.compare(other) > 0
  288 
  289     def __ge__(self, other):
  290         return self.compare(other) >= 0
  291 
  292     def __pos__(self):
  293         common_divisor = theIntegerRing.gcd(self.numerator, self.denominator)
  294         if common_divisor != 1:
  295             self.numerator //= common_divisor
  296             self.denominator //= common_divisor
  297         return Rational(self.numerator, self.denominator)
  298 
  299     def __neg__(self):
  300         return Rational(-self.numerator, self.denominator)
  301 
  302     def __abs__(self):
  303         return +Rational(abs(self.numerator), self.denominator)
  304 
  305     def __long__(self):
  306         return self.numerator // self.denominator
  307 
  308     __int__ = __long__
  309 
  310     def __str__(self):
  311         return str(self.numerator) + "/" + str(self.denominator)
  312 
  313     def __repr__(self):
  314         return "%s(%d, %d)" % (self.__class__.__name__, self.numerator, self.denominator)
  315 
  316     def __nonzero__(self):
  317         if self.numerator:
  318             return True
  319         else:
  320             return False
  321 
  322     def __hash__(self):
  323         """
  324         a==b => hash(a)==hash(b)
  325         """
  326         hashed = hash(self.__class__.__name__)
  327         if self.numerator % self.denominator == 0:
  328             hashed ^= hash(self.numerator // self.denominator)
  329         else:
  330             hashed ^= hash(self.numerator)
  331             hashed ^= hash(self.denominator)
  332         return hashed
  333 
  334     def expand(self, base, limit):
  335         """
  336         r.expand(k, limit) returns the nearest rational number whose
  337         denominator is a power of k and at most limit, if k > 0.  if
  338         k==0, it returns the nearest rational number whose denominator
  339         is at most limit, i.e. r.expand(0, limit) == r.trim(limit).
  340         """
  341         if base == 0:
  342             return self.trim(limit)
  343         assert isIntegerObject(base) and base > 0
  344         if self < 0:
  345             return -(-self).expand(base, limit)
  346         numerator, rest = divmod(self.numerator, self.denominator)
  347         i = 0
  348         if base == 2:
  349             while numerator*2 <= limit and rest:
  350                 numerator <<= 1
  351                 rest <<= 1
  352                 i += 1
  353                 if rest >= self.denominator:
  354                     numerator += 1
  355                     rest -= self.denominator
  356             if rest*2 > self.denominator:
  357                 numerator += 1
  358         else:
  359             while numerator*base <= limit and rest:
  360                 numerator *= base
  361                 rest *= base
  362                 i += 1
  363                 while rest >= self.denominator:
  364                     numerator += 1
  365                     rest -= self.denominator
  366             if rest*2 > self.denominator:
  367                 numerator += 1
  368         return Rational(numerator, base ** i)
  369 
  370     def trim(self, max_denominator):
  371         quotient, remainder = divmod(self.numerator, self.denominator)
  372         approximant0 = Rational(quotient, 1)
  373         if remainder == 0:
  374             return approximant0
  375         rest = Rational(remainder, self.denominator)
  376         quotient, remainder = divmod(rest.denominator, rest.numerator)
  377         if quotient > max_denominator:
  378             return approximant0
  379         approximant1 = Rational(quotient * approximant0.numerator + 1, quotient)
  380         if remainder == 0:
  381             return approximant1
  382         rest = Rational(remainder, rest.numerator)
  383         while remainder:
  384             if rest.numerator > 1:
  385                 quotient, remainder = divmod(rest.denominator, rest.numerator)
  386             elif rest.denominator > 1:
  387                 quotient, remainder = (rest.denominator-1, 1)
  388             else:
  389                 quotient, remainder = (1, 0)
  390             approximant = Rational(quotient * approximant1.numerator + approximant0.numerator, quotient * approximant1.denominator + approximant0.denominator)
  391             if approximant.denominator > max_denominator:
  392                 break
  393             approximant0, approximant1 = approximant1, approximant
  394             rest = Rational(remainder, rest.numerator)
  395         return approximant1
  396 
  397     def compare(self, other):
  398         if isIntegerObject(other):
  399             return self.numerator - self.denominator * other
  400         if isinstance(other, float):
  401             return self.compare(Rational(other))
  402         if isinstance(other, Float):
  403             return cmp(self.toFloat(), other)
  404         return self.numerator*other.denominator - self.denominator*other.numerator
  405 
  406     def getRing(self):
  407         return theRationalField
  408 
  409     def _reduce(self):
  410         if self.denominator < 0:
  411             self.numerator = -self.numerator
  412             self.denominator = -self.denominator
  413         common_divisor = theIntegerRing.gcd(self.numerator, self.denominator)
  414         if common_divisor != 1:
  415             self.numerator //= common_divisor
  416             self.denominator //= common_divisor
  417     def __float__(self):
  418         return float(self.decimalString(17))
  419 
  420     def toFloat(self):
  421         return Float(self.numerator) / Float(self.denominator)
  422 
  423     def decimalString(self, N):
  424         """
  425         Return a string of the number to N decimal places.
  426         """
  427         n = self.numerator
  428         d = self.denominator
  429         L = []
  430         if n < 0:
  431             L.append('-')
  432             n = -n
  433         i = 1
  434         L.append(str(n//d))
  435         L.append('.')
  436         while i <= N:
  437             n = n % d * 10
  438             L.append(str(n//d))
  439             i += 1
  440         return ''.join(L)
  441 
  442     def _init_by_Rational_Rational(self, numerator, denominator):
  443         """
  444         Initialize by a rational numbers.
  445         """
  446         self.numerator = numerator.numerator * denominator.denominator
  447         self.denominator = numerator.denominator * denominator.numerator
  448 
  449     def _init_by_float_Rational(self, numerator, denominator):
  450         """
  451         Initialize by a float number and a rational number.
  452         """
  453         dp = 53
  454         frexp = math.frexp(numerator)
  455         self.numerator = denominator.denominator * (frexp[0] * 2 ** dp)
  456         self.denominator = denominator.numerator * (2 ** (dp - frexp[1]))
  457 
  458     def _init_by_int_Rational(self, numerator, denominator):
  459         """
  460         Initailize by an integer and a rational number.
  461         """
  462         self.numerator = denominator.denominator * numerator
  463         self.denominator = denominator.numerator
  464 
  465     def _init_by_Rational_float(self, numerator, denominator):
  466         """
  467         Initialize by a rational number and a float.
  468         """
  469         dp = 53
  470         frexp = math.frexp(denominator)
  471         self.numerator = numerator.numerator * (2 ** (dp - frexp[1]))
  472         self.denominator = numerator.denominator * (frexp[0] * 2 ** dp)
  473 
  474     def _init_by_float_float(self, numerator, denominator):
  475         """
  476         Initialize by a float numbers.
  477         """
  478         dp = 53
  479         frexp_num = math.frexp(numerator)
  480         frexp_den = math.frexp(denominator)
  481         self.numerator = Integer(frexp_num[0] * 2 ** (2 * dp - frexp_den[1]))
  482         self.denominator = Integer(frexp_den[0] * 2 ** (2 * dp - frexp_num[1]))
  483 
  484     def _init_by_int_float(self, numerator, denominator):
  485         """
  486         Initailize by an integer and a float
  487         """
  488         dp = 53
  489         frexp_den = math.frexp(denominator)
  490         self.numerator = Integer(numerator * (2 ** (dp - frexp_den[1])))
  491         self.denominator = Integer(frexp_den[0] * 2 ** dp)
  492 
  493     def _init_by_Rational_int(self, numerator, denominator):
  494         """
  495         Initialize by a rational number and integer.
  496         """
  497         self.numerator = numerator.numerator
  498         self.denominator = numerator.denominator * denominator
  499 
  500     def _init_by_float_int(self, numerator, denominator):
  501         """
  502         Initialize by a float number and an integer.
  503         """
  504         dp = 53
  505         frexp = math.frexp(numerator)
  506         self.numerator = Integer(frexp[0] * 2 ** dp)
  507         self.denominator = Integer(2 ** (dp - frexp[1]) * denominator)
  508 
  509     def _init_by_int_int(self, numerator, denominator):
  510         """
  511         Initailize by an integers.
  512         """
  513         self.numerator = Integer(numerator)
  514         self.denominator = Integer(denominator)
  515 
  516 
  517 class RationalField (ring.QuotientField):
  518     """
  519     RationalField is a class of field of rationals.
  520     The class has the single instance 'theRationalField'.
  521     """
  522 
  523     def __init__(self):
  524         ring.QuotientField.__init__(self, theIntegerRing)
  525 
  526     def __contains__(self, element):
  527         try:
  528             reduced = +element
  529             return (isinstance(reduced, Rational) or isIntegerObject(reduced))
  530         except (TypeError, AttributeError):
  531             return False
  532 
  533     def __eq__(self, other):
  534         """
  535         Equality test.
  536         """
  537         return isinstance(other, RationalField)
  538 
  539     def classNumber(self):
  540         """The class number of the rational field is one."""
  541         return 1
  542 
  543     def getQuotientField(self):
  544         """getQuotientField returns the rational field itself."""
  545         return self
  546 
  547     def getCharacteristic(self):
  548         """The characteristic of the rational field is zero."""
  549         return 0
  550 
  551     def createElement(self, numerator, denominator=1):
  552         """
  553         createElement returns a Rational object.
  554         If the number of arguments is one, it must be an integer or a rational.
  555         If the number of arguments is two, they must be integers.
  556         """
  557         return Rational(numerator, denominator)
  558 
  559     def __str__(self):
  560         return "Q"
  561 
  562     def __repr__(self):
  563         return "RationalField()"
  564 
  565     def __hash__(self):
  566         """
  567         Return a hash number (always 1).
  568         """
  569         return 1
  570 
  571     def issubring(self, other):
  572         """
  573         reports whether another ring contains the rational field as
  574         subring.
  575 
  576         If other is also the rational field, the output is True.  If
  577         other is the integer ring, the output is False.  In other
  578         cases it depends on the implementation of another ring's
  579         issuperring method.
  580         """
  581         if isinstance(other, RationalField):
  582             return True
  583         elif isinstance(other, IntegerRing):
  584             return False
  585         try:
  586             return other.issuperring(self)
  587         except RuntimeError:
  588             # reached recursion limit by calling on each other
  589             raise NotImplementedError("no common super ring")
  590 
  591     def issuperring(self, other):
  592         """
  593         reports whether the rational number field contains another
  594         ring as subring.
  595 
  596         If other is also the rational number field or the ring of
  597         integer, the output is True.  In other cases it depends on the
  598         implementation of another ring's issubring method.
  599         """
  600         if isinstance(other, (RationalField, IntegerRing)):
  601             return True
  602         try:
  603             return other.issubring(self)
  604         except RuntimeError:
  605             # reached recursion limit by calling on each other
  606             raise NotImplementedError("no common super ring")
  607 
  608     def getCommonSuperring(self, other):
  609         """
  610         Return common superring of the ring and another ring.
  611         """
  612         if self.issubring(other):
  613             return other
  614         elif self.issuperring(other):
  615             return self
  616         try:
  617             return other.getCommonSuperring(self)
  618         except RuntimeError:
  619             # reached recursion limit by calling on each other
  620             raise NotImplementedError("no common super ring")
  621 
  622     def _getOne(self):
  623         "getter for one"
  624         if self._one is None:
  625             self._one = Rational(1, 1)
  626         return self._one
  627 
  628     one = property(_getOne, None, None, "multiplicative unit.")
  629 
  630     def _getZero(self):
  631         "getter for zero"
  632         if self._zero is None:
  633             self._zero = Rational(0, 1)
  634         return self._zero
  635 
  636     zero = property(_getZero, None, None, "additive unit.")
  637 
  638 
  639 class Integer(long, ring.CommutativeRingElement):
  640     """
  641     Integer is a class of integer.  Since 'int' and 'long' do not
  642     return rational for division, it is needed to create a new class.
  643     """
  644     def __init__(self, value):
  645         ring.CommutativeRingElement.__init__(self)
  646 
  647     def __div__(self, other):
  648         if other in theIntegerRing:
  649             return +Rational(self, +other)
  650         else:
  651             return NotImplemented
  652 
  653     def __rdiv__(self, other):
  654         if other in theIntegerRing:
  655             return +Rational(+other, self)
  656         else:
  657             return NotImplemented
  658 
  659     __truediv__ = __div__
  660 
  661     __rtruediv__ = __rdiv__
  662 
  663     def __floordiv__(self, other):
  664         return Integer(long(self)//other)
  665 
  666     def __rfloordiv__(self, other):
  667         try:
  668             return Integer(other//long(self))
  669         except:
  670             return NotImplemented
  671 
  672     def __mod__(self, other):
  673         if isinstance(other, (int, long)):
  674             return Integer(long(self)%long(other))
  675         return NotImplemented
  676 
  677     def __rmod__(self, other):
  678         return Integer(other%long(self))
  679 
  680     def __divmod__(self, other):
  681         return tuple([Integer(x) for x in divmod(long(self), other)])
  682 
  683     def __rdivmod__(self, other):
  684         return tuple([Integer(x) for x in divmod(other, long(self))])
  685 
  686     def __add__(self, other):
  687         if isIntegerObject(other):
  688             return Integer(long(self)+other)
  689         else:
  690             return NotImplemented
  691 
  692     __radd__ = __add__
  693 
  694     def __sub__(self, other):
  695         if isIntegerObject(other):
  696             return Integer(long(self)-other)
  697         else:
  698             return NotImplemented
  699 
  700     def __rsub__(self, other):
  701         return Integer(other-long(self))
  702 
  703     def __mul__(self, other):
  704         if isinstance(other, (int, long)):
  705             return self.__class__(long(self) * other)
  706         try:
  707             retval = other.__rmul__(self)
  708             if retval is not NotImplemented:
  709                 return retval
  710         except Exception:
  711             pass
  712         return self.actAdditive(other)
  713 
  714     def __rmul__(self, other):
  715         if isinstance(other, (int, long)):
  716             return self.__class__(other * long(self))
  717         elif other.__class__ in __builtins__.values():
  718             return other.__mul__(long(self))
  719         return self.actAdditive(other)
  720 
  721     def __pow__(self, index, modulo=None):
  722         """
  723         If index is negative, result may be a rational number.
  724         """
  725         if modulo is None and index < 0:
  726             return Rational(1, long(self) ** (-index))
  727         return Integer(pow(long(self), index, modulo))
  728 
  729     def __pos__(self):
  730         return Integer(self)
  731 
  732     def __neg__(self):
  733         return Integer(-long(self))
  734 
  735     def __abs__(self):
  736         return Integer(abs(long(self)))
  737 
  738     def __eq__(self, other):
  739         return long(self) == long(other)
  740 
  741     def __hash__(self):
  742         return hash(long(self))
  743 
  744     def getRing(self):
  745         return theIntegerRing
  746 
  747     def inverse(self):
  748         return Rational(1, self)
  749 
  750     def actAdditive(self, other):
  751         """
  752         Act on other additively, i.e. n is expanded to n time
  753         additions of other.  Naively, it is:
  754           return sum([+other for _ in xrange(self)])
  755         but, here we use a binary addition chain.
  756         """
  757         nonneg, absVal = (self >= 0), abs(self)
  758         result = 0
  759         doubling = +other
  760         while absVal:
  761             if absVal & 1:
  762                 result += doubling
  763             doubling += doubling
  764             absVal >>= 1
  765         if not nonneg:
  766             result = -result
  767         return result
  768 
  769     def actMultiplicative(self, other):
  770         """
  771         Act on other multiplicatively, i.e. n is expanded to n time
  772         multiplications of other.  Naively, it is:
  773           return reduce(lambda x,y:x*y, [+other for _ in xrange(self)])
  774         but, here we use a binary addition chain.
  775         """
  776         nonneg, absVal = (self >= 0), abs(self)
  777         result = 1
  778         doubling = +other
  779         while absVal:
  780             if absVal& 1:
  781                 result *= doubling
  782             doubling *= doubling
  783             absVal >>= 1
  784         if not nonneg:
  785             result = result.inverse()
  786         return result
  787 
  788 
  789 class IntegerRing (ring.CommutativeRing):
  790     """
  791     IntegerRing is a class of ring of rational integers.
  792     The class has the single instance 'theIntegerRing'.
  793     """
  794 
  795     def __init__(self):
  796         ring.CommutativeRing.__init__(self)
  797         self.properties.setIseuclidean(True)
  798         self.properties.setIsfield(False)
  799 
  800     def __contains__(self, element):
  801         """
  802         `in' operator is provided for checking an object be in the
  803         rational integer ring mathematically.  To check an object be
  804         an integer object in Python, please use isIntegerObject.
  805         """
  806         try:
  807             return isIntegerObject(+element)
  808         except (TypeError, AttributeError):
  809             return False
  810 
  811     def __eq__(self, other):
  812         """
  813         Equality test.
  814         """
  815         return isinstance(other, IntegerRing)
  816 
  817     def getQuotientField(self):
  818         """
  819         getQuotientField returns the rational field.
  820         """
  821         return theRationalField
  822 
  823     def createElement(self, seed):
  824         """
  825         createElement returns an Integer object with seed,
  826         which must be an integer.
  827         """
  828         return Integer(seed)
  829 
  830     def __str__(self):
  831         return "Z"
  832 
  833     def __repr__(self):
  834         return "IntegerRing()"
  835 
  836     def __hash__(self):
  837         """
  838         Return a hash number (always 0).
  839         """
  840         return 0
  841 
  842     def getCharacteristic(self):
  843         """
  844         The characteristic of the integer ring is zero.
  845         """
  846         return 0
  847 
  848     def issubring(self, other):
  849         """
  850         reports whether another ring contains the integer ring as
  851         subring.
  852 
  853         If other is also the integer ring, the output is True.  In
  854         other cases it depends on the implementation of another ring's
  855         issuperring method.
  856         """
  857         if isinstance(other, IntegerRing):
  858             return True
  859         return other.issuperring(self)
  860 
  861     def issuperring(self, other):
  862         """
  863         reports whether the integer ring contains another ring as
  864         subring.
  865 
  866         If other is also the integer ring, the output is True.  In
  867         other cases it depends on the implementation of another ring's
  868         issubring method.
  869         """
  870         if isinstance(other, IntegerRing):
  871             return True
  872         return other.issubring(self)
  873 
  874     def getCommonSuperring(self, other):
  875         """
  876         Return common superring of the ring and another ring.
  877         """
  878         if self.issubring(other):
  879             return other
  880         elif self.issuperring(other):
  881             return self
  882         try:
  883             return other.getCommonSuperring(self)
  884         except RuntimeError:
  885             # reached recursion limit by calling on each other
  886             raise NotImplementedError("no common super ring")
  887 
  888     def gcd(self, n, m):
  889         """
  890         Return the greatest common divisor of given 2 integers.
  891         """
  892         a, b = abs(n), abs(m)
  893         return Integer(gcd.gcd(a, b))
  894 
  895     def lcm(self, a, b):
  896         """
  897         Return the least common multiple of given 2 integers.
  898         If both are zero, it raises an exception.
  899         """
  900         return a // self.gcd(a, b) * b
  901 
  902     def extgcd(self, a, b):
  903         """
  904         Return a tuple (u, v, d); they are the greatest common divisor
  905         d of two given integers x and y and u, v such that
  906         d = x * u + y * v.
  907         """
  908         return tuple(map(Integer, gcd.extgcd(a, b)))
  909 
  910     def _getOne(self):
  911         "getter for one"
  912         if self._one is None:
  913             self._one = Integer(1)
  914         return self._one
  915 
  916     one = property(_getOne, None, None, "multiplicative unit.")
  917 
  918     def _getZero(self):
  919         "getter for zero"
  920         if self._zero is None:
  921             self._zero = Integer(0)
  922         return self._zero
  923 
  924     zero = property(_getZero, None, None, "additive unit.")
  925 
  926 
  927 theIntegerRing = IntegerRing()
  928 theRationalField = RationalField()
  929 
  930 
  931 def isIntegerObject(anObject):
  932     """
  933     True if the given object is instance of int or long,
  934     False otherwise.
  935     """
  936     return isinstance(anObject, (int, long))
  937 
  938 def IntegerIfIntOrLong(anObject):
  939     """
  940     Cast int or long objects to Integer.
  941     The objects in list or tuple can be casted also.
  942     """
  943     objectClass = anObject.__class__
  944     if objectClass == int or objectClass == long:
  945         return Integer(anObject)
  946     elif isinstance(anObject, (list,tuple)):
  947         return objectClass([IntegerIfIntOrLong(i) for i in anObject])
  948     return anObject
  949 
  950 ##
  951 def continued_fraction_expansion(target, terms):
  952     """
  953     Return continued fraction expansion of a real number.
  954 
  955     >>> continued_fraction_expansion(1.4142, 2)
  956     [1, 2, 2]
  957 
  958     The first component is the integer part, and rest is fractional
  959     part, whose number of terms is specified by the second argument.
  960     """
  961     # integer part
  962     ipart = math.floor(target)
  963     target -= ipart
  964     result = [int(ipart)]
  965 
  966     # expansion
  967     for i in range(terms):
  968         reverse = 1 / target
  969         term = math.floor(reverse)
  970         target = reverse - term
  971         result.append(int(term))
  972 
  973     return result