Spaces:
Sleeping
Sleeping
| """ | |
| PythonMPQ: Rational number type based on Python integers. | |
| This class is intended as a pure Python fallback for when gmpy2 is not | |
| installed. If gmpy2 is installed then its mpq type will be used instead. The | |
| mpq type is around 20x faster. We could just use the stdlib Fraction class | |
| here but that is slower: | |
| from fractions import Fraction | |
| from sympy.external.pythonmpq import PythonMPQ | |
| nums = range(1000) | |
| dens = range(5, 1005) | |
| rats = [Fraction(n, d) for n, d in zip(nums, dens)] | |
| sum(rats) # <--- 24 milliseconds | |
| rats = [PythonMPQ(n, d) for n, d in zip(nums, dens)] | |
| sum(rats) # <--- 7 milliseconds | |
| Both mpq and Fraction have some awkward features like the behaviour of | |
| division with // and %: | |
| >>> from fractions import Fraction | |
| >>> Fraction(2, 3) % Fraction(1, 4) | |
| 1/6 | |
| For the QQ domain we do not want this behaviour because there should be no | |
| remainder when dividing rational numbers. SymPy does not make use of this | |
| aspect of mpq when gmpy2 is installed. Since this class is a fallback for that | |
| case we do not bother implementing e.g. __mod__ so that we can be sure we | |
| are not using it when gmpy2 is installed either. | |
| """ | |
| import operator | |
| from math import gcd | |
| from decimal import Decimal | |
| from fractions import Fraction | |
| import sys | |
| from typing import Tuple as tTuple, Type | |
| # Used for __hash__ | |
| _PyHASH_MODULUS = sys.hash_info.modulus | |
| _PyHASH_INF = sys.hash_info.inf | |
| class PythonMPQ: | |
| """Rational number implementation that is intended to be compatible with | |
| gmpy2's mpq. | |
| Also slightly faster than fractions.Fraction. | |
| PythonMPQ should be treated as immutable although no effort is made to | |
| prevent mutation (since that might slow down calculations). | |
| """ | |
| __slots__ = ('numerator', 'denominator') | |
| def __new__(cls, numerator, denominator=None): | |
| """Construct PythonMPQ with gcd computation and checks""" | |
| if denominator is not None: | |
| # | |
| # PythonMPQ(n, d): require n and d to be int and d != 0 | |
| # | |
| if isinstance(numerator, int) and isinstance(denominator, int): | |
| # This is the slow part: | |
| divisor = gcd(numerator, denominator) | |
| numerator //= divisor | |
| denominator //= divisor | |
| return cls._new_check(numerator, denominator) | |
| else: | |
| # | |
| # PythonMPQ(q) | |
| # | |
| # Here q can be PythonMPQ, int, Decimal, float, Fraction or str | |
| # | |
| if isinstance(numerator, int): | |
| return cls._new(numerator, 1) | |
| elif isinstance(numerator, PythonMPQ): | |
| return cls._new(numerator.numerator, numerator.denominator) | |
| # Let Fraction handle Decimal/float conversion and str parsing | |
| if isinstance(numerator, (Decimal, float, str)): | |
| numerator = Fraction(numerator) | |
| if isinstance(numerator, Fraction): | |
| return cls._new(numerator.numerator, numerator.denominator) | |
| # | |
| # Reject everything else. This is more strict than mpq which allows | |
| # things like mpq(Fraction, Fraction) or mpq(Decimal, any). The mpq | |
| # behaviour is somewhat inconsistent so we choose to accept only a | |
| # more strict subset of what mpq allows. | |
| # | |
| raise TypeError("PythonMPQ() requires numeric or string argument") | |
| def _new_check(cls, numerator, denominator): | |
| """Construct PythonMPQ, check divide by zero and canonicalize signs""" | |
| if not denominator: | |
| raise ZeroDivisionError(f'Zero divisor {numerator}/{denominator}') | |
| elif denominator < 0: | |
| numerator = -numerator | |
| denominator = -denominator | |
| return cls._new(numerator, denominator) | |
| def _new(cls, numerator, denominator): | |
| """Construct PythonMPQ efficiently (no checks)""" | |
| obj = super().__new__(cls) | |
| obj.numerator = numerator | |
| obj.denominator = denominator | |
| return obj | |
| def __int__(self): | |
| """Convert to int (truncates towards zero)""" | |
| p, q = self.numerator, self.denominator | |
| if p < 0: | |
| return -(-p//q) | |
| return p//q | |
| def __float__(self): | |
| """Convert to float (approximately)""" | |
| return self.numerator / self.denominator | |
| def __bool__(self): | |
| """True/False if nonzero/zero""" | |
| return bool(self.numerator) | |
| def __eq__(self, other): | |
| """Compare equal with PythonMPQ, int, float, Decimal or Fraction""" | |
| if isinstance(other, PythonMPQ): | |
| return (self.numerator == other.numerator | |
| and self.denominator == other.denominator) | |
| elif isinstance(other, self._compatible_types): | |
| return self.__eq__(PythonMPQ(other)) | |
| else: | |
| return NotImplemented | |
| def __hash__(self): | |
| """hash - same as mpq/Fraction""" | |
| try: | |
| dinv = pow(self.denominator, -1, _PyHASH_MODULUS) | |
| except ValueError: | |
| hash_ = _PyHASH_INF | |
| else: | |
| hash_ = hash(hash(abs(self.numerator)) * dinv) | |
| result = hash_ if self.numerator >= 0 else -hash_ | |
| return -2 if result == -1 else result | |
| def __reduce__(self): | |
| """Deconstruct for pickling""" | |
| return type(self), (self.numerator, self.denominator) | |
| def __str__(self): | |
| """Convert to string""" | |
| if self.denominator != 1: | |
| return f"{self.numerator}/{self.denominator}" | |
| else: | |
| return f"{self.numerator}" | |
| def __repr__(self): | |
| """Convert to string""" | |
| return f"MPQ({self.numerator},{self.denominator})" | |
| def _cmp(self, other, op): | |
| """Helper for lt/le/gt/ge""" | |
| if not isinstance(other, self._compatible_types): | |
| return NotImplemented | |
| lhs = self.numerator * other.denominator | |
| rhs = other.numerator * self.denominator | |
| return op(lhs, rhs) | |
| def __lt__(self, other): | |
| """self < other""" | |
| return self._cmp(other, operator.lt) | |
| def __le__(self, other): | |
| """self <= other""" | |
| return self._cmp(other, operator.le) | |
| def __gt__(self, other): | |
| """self > other""" | |
| return self._cmp(other, operator.gt) | |
| def __ge__(self, other): | |
| """self >= other""" | |
| return self._cmp(other, operator.ge) | |
| def __abs__(self): | |
| """abs(q)""" | |
| return self._new(abs(self.numerator), self.denominator) | |
| def __pos__(self): | |
| """+q""" | |
| return self | |
| def __neg__(self): | |
| """-q""" | |
| return self._new(-self.numerator, self.denominator) | |
| def __add__(self, other): | |
| """q1 + q2""" | |
| if isinstance(other, PythonMPQ): | |
| # | |
| # This is much faster than the naive method used in the stdlib | |
| # fractions module. Not sure where this method comes from | |
| # though... | |
| # | |
| # Compare timings for something like: | |
| # nums = range(1000) | |
| # rats = [PythonMPQ(n, d) for n, d in zip(nums[:-5], nums[5:])] | |
| # sum(rats) # <-- time this | |
| # | |
| ap, aq = self.numerator, self.denominator | |
| bp, bq = other.numerator, other.denominator | |
| g = gcd(aq, bq) | |
| if g == 1: | |
| p = ap*bq + aq*bp | |
| q = bq*aq | |
| else: | |
| q1, q2 = aq//g, bq//g | |
| p, q = ap*q2 + bp*q1, q1*q2 | |
| g2 = gcd(p, g) | |
| p, q = (p // g2), q * (g // g2) | |
| elif isinstance(other, int): | |
| p = self.numerator + self.denominator * other | |
| q = self.denominator | |
| else: | |
| return NotImplemented | |
| return self._new(p, q) | |
| def __radd__(self, other): | |
| """z1 + q2""" | |
| if isinstance(other, int): | |
| p = self.numerator + self.denominator * other | |
| q = self.denominator | |
| return self._new(p, q) | |
| else: | |
| return NotImplemented | |
| def __sub__(self ,other): | |
| """q1 - q2""" | |
| if isinstance(other, PythonMPQ): | |
| ap, aq = self.numerator, self.denominator | |
| bp, bq = other.numerator, other.denominator | |
| g = gcd(aq, bq) | |
| if g == 1: | |
| p = ap*bq - aq*bp | |
| q = bq*aq | |
| else: | |
| q1, q2 = aq//g, bq//g | |
| p, q = ap*q2 - bp*q1, q1*q2 | |
| g2 = gcd(p, g) | |
| p, q = (p // g2), q * (g // g2) | |
| elif isinstance(other, int): | |
| p = self.numerator - self.denominator*other | |
| q = self.denominator | |
| else: | |
| return NotImplemented | |
| return self._new(p, q) | |
| def __rsub__(self, other): | |
| """z1 - q2""" | |
| if isinstance(other, int): | |
| p = self.denominator * other - self.numerator | |
| q = self.denominator | |
| return self._new(p, q) | |
| else: | |
| return NotImplemented | |
| def __mul__(self, other): | |
| """q1 * q2""" | |
| if isinstance(other, PythonMPQ): | |
| ap, aq = self.numerator, self.denominator | |
| bp, bq = other.numerator, other.denominator | |
| x1 = gcd(ap, bq) | |
| x2 = gcd(bp, aq) | |
| p, q = ((ap//x1)*(bp//x2), (aq//x2)*(bq//x1)) | |
| elif isinstance(other, int): | |
| x = gcd(other, self.denominator) | |
| p = self.numerator*(other//x) | |
| q = self.denominator//x | |
| else: | |
| return NotImplemented | |
| return self._new(p, q) | |
| def __rmul__(self, other): | |
| """z1 * q2""" | |
| if isinstance(other, int): | |
| x = gcd(self.denominator, other) | |
| p = self.numerator*(other//x) | |
| q = self.denominator//x | |
| return self._new(p, q) | |
| else: | |
| return NotImplemented | |
| def __pow__(self, exp): | |
| """q ** z""" | |
| p, q = self.numerator, self.denominator | |
| if exp < 0: | |
| p, q, exp = q, p, -exp | |
| return self._new_check(p**exp, q**exp) | |
| def __truediv__(self, other): | |
| """q1 / q2""" | |
| if isinstance(other, PythonMPQ): | |
| ap, aq = self.numerator, self.denominator | |
| bp, bq = other.numerator, other.denominator | |
| x1 = gcd(ap, bp) | |
| x2 = gcd(bq, aq) | |
| p, q = ((ap//x1)*(bq//x2), (aq//x2)*(bp//x1)) | |
| elif isinstance(other, int): | |
| x = gcd(other, self.numerator) | |
| p = self.numerator//x | |
| q = self.denominator*(other//x) | |
| else: | |
| return NotImplemented | |
| return self._new_check(p, q) | |
| def __rtruediv__(self, other): | |
| """z / q""" | |
| if isinstance(other, int): | |
| x = gcd(self.numerator, other) | |
| p = self.denominator*(other//x) | |
| q = self.numerator//x | |
| return self._new_check(p, q) | |
| else: | |
| return NotImplemented | |
| _compatible_types: tTuple[Type, ...] = () | |
| # | |
| # These are the types that PythonMPQ will interoperate with for operations | |
| # and comparisons such as ==, + etc. We define this down here so that we can | |
| # include PythonMPQ in the list as well. | |
| # | |
| PythonMPQ._compatible_types = (PythonMPQ, int, Decimal, Fraction) | |