+++ /dev/null
-# Originally contributed by Sjoerd Mullender.\r
-# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>.\r
-\r
-"""Rational, infinite-precision, real numbers."""\r
-\r
-from __future__ import division\r
-from decimal import Decimal\r
-import math\r
-import numbers\r
-import operator\r
-import re\r
-\r
-__all__ = ['Fraction', 'gcd']\r
-\r
-Rational = numbers.Rational\r
-\r
-\r
-def gcd(a, b):\r
- """Calculate the Greatest Common Divisor of a and b.\r
-\r
- Unless b==0, the result will have the same sign as b (so that when\r
- b is divided by it, the result comes out positive).\r
- """\r
- while b:\r
- a, b = b, a%b\r
- return a\r
-\r
-\r
-_RATIONAL_FORMAT = re.compile(r"""\r
- \A\s* # optional whitespace at the start, then\r
- (?P<sign>[-+]?) # an optional sign, then\r
- (?=\d|\.\d) # lookahead for digit or .digit\r
- (?P<num>\d*) # numerator (possibly empty)\r
- (?: # followed by\r
- (?:/(?P<denom>\d+))? # an optional denominator\r
- | # or\r
- (?:\.(?P<decimal>\d*))? # an optional fractional part\r
- (?:E(?P<exp>[-+]?\d+))? # and optional exponent\r
- )\r
- \s*\Z # and optional whitespace to finish\r
-""", re.VERBOSE | re.IGNORECASE)\r
-\r
-\r
-class Fraction(Rational):\r
- """This class implements rational numbers.\r
-\r
- In the two-argument form of the constructor, Fraction(8, 6) will\r
- produce a rational number equivalent to 4/3. Both arguments must\r
- be Rational. The numerator defaults to 0 and the denominator\r
- defaults to 1 so that Fraction(3) == 3 and Fraction() == 0.\r
-\r
- Fractions can also be constructed from:\r
-\r
- - numeric strings similar to those accepted by the\r
- float constructor (for example, '-2.3' or '1e10')\r
-\r
- - strings of the form '123/456'\r
-\r
- - float and Decimal instances\r
-\r
- - other Rational instances (including integers)\r
-\r
- """\r
-\r
- __slots__ = ('_numerator', '_denominator')\r
-\r
- # We're immutable, so use __new__ not __init__\r
- def __new__(cls, numerator=0, denominator=None):\r
- """Constructs a Fraction.\r
-\r
- Takes a string like '3/2' or '1.5', another Rational instance, a\r
- numerator/denominator pair, or a float.\r
-\r
- Examples\r
- --------\r
-\r
- >>> Fraction(10, -8)\r
- Fraction(-5, 4)\r
- >>> Fraction(Fraction(1, 7), 5)\r
- Fraction(1, 35)\r
- >>> Fraction(Fraction(1, 7), Fraction(2, 3))\r
- Fraction(3, 14)\r
- >>> Fraction('314')\r
- Fraction(314, 1)\r
- >>> Fraction('-35/4')\r
- Fraction(-35, 4)\r
- >>> Fraction('3.1415') # conversion from numeric string\r
- Fraction(6283, 2000)\r
- >>> Fraction('-47e-2') # string may include a decimal exponent\r
- Fraction(-47, 100)\r
- >>> Fraction(1.47) # direct construction from float (exact conversion)\r
- Fraction(6620291452234629, 4503599627370496)\r
- >>> Fraction(2.25)\r
- Fraction(9, 4)\r
- >>> Fraction(Decimal('1.47'))\r
- Fraction(147, 100)\r
-\r
- """\r
- self = super(Fraction, cls).__new__(cls)\r
-\r
- if denominator is None:\r
- if isinstance(numerator, Rational):\r
- self._numerator = numerator.numerator\r
- self._denominator = numerator.denominator\r
- return self\r
-\r
- elif isinstance(numerator, float):\r
- # Exact conversion from float\r
- value = Fraction.from_float(numerator)\r
- self._numerator = value._numerator\r
- self._denominator = value._denominator\r
- return self\r
-\r
- elif isinstance(numerator, Decimal):\r
- value = Fraction.from_decimal(numerator)\r
- self._numerator = value._numerator\r
- self._denominator = value._denominator\r
- return self\r
-\r
- elif isinstance(numerator, basestring):\r
- # Handle construction from strings.\r
- m = _RATIONAL_FORMAT.match(numerator)\r
- if m is None:\r
- raise ValueError('Invalid literal for Fraction: %r' %\r
- numerator)\r
- numerator = int(m.group('num') or '0')\r
- denom = m.group('denom')\r
- if denom:\r
- denominator = int(denom)\r
- else:\r
- denominator = 1\r
- decimal = m.group('decimal')\r
- if decimal:\r
- scale = 10**len(decimal)\r
- numerator = numerator * scale + int(decimal)\r
- denominator *= scale\r
- exp = m.group('exp')\r
- if exp:\r
- exp = int(exp)\r
- if exp >= 0:\r
- numerator *= 10**exp\r
- else:\r
- denominator *= 10**-exp\r
- if m.group('sign') == '-':\r
- numerator = -numerator\r
-\r
- else:\r
- raise TypeError("argument should be a string "\r
- "or a Rational instance")\r
-\r
- elif (isinstance(numerator, Rational) and\r
- isinstance(denominator, Rational)):\r
- numerator, denominator = (\r
- numerator.numerator * denominator.denominator,\r
- denominator.numerator * numerator.denominator\r
- )\r
- else:\r
- raise TypeError("both arguments should be "\r
- "Rational instances")\r
-\r
- if denominator == 0:\r
- raise ZeroDivisionError('Fraction(%s, 0)' % numerator)\r
- g = gcd(numerator, denominator)\r
- self._numerator = numerator // g\r
- self._denominator = denominator // g\r
- return self\r
-\r
- @classmethod\r
- def from_float(cls, f):\r
- """Converts a finite float to a rational number, exactly.\r
-\r
- Beware that Fraction.from_float(0.3) != Fraction(3, 10).\r
-\r
- """\r
- if isinstance(f, numbers.Integral):\r
- return cls(f)\r
- elif not isinstance(f, float):\r
- raise TypeError("%s.from_float() only takes floats, not %r (%s)" %\r
- (cls.__name__, f, type(f).__name__))\r
- if math.isnan(f) or math.isinf(f):\r
- raise TypeError("Cannot convert %r to %s." % (f, cls.__name__))\r
- return cls(*f.as_integer_ratio())\r
-\r
- @classmethod\r
- def from_decimal(cls, dec):\r
- """Converts a finite Decimal instance to a rational number, exactly."""\r
- from decimal import Decimal\r
- if isinstance(dec, numbers.Integral):\r
- dec = Decimal(int(dec))\r
- elif not isinstance(dec, Decimal):\r
- raise TypeError(\r
- "%s.from_decimal() only takes Decimals, not %r (%s)" %\r
- (cls.__name__, dec, type(dec).__name__))\r
- if not dec.is_finite():\r
- # Catches infinities and nans.\r
- raise TypeError("Cannot convert %s to %s." % (dec, cls.__name__))\r
- sign, digits, exp = dec.as_tuple()\r
- digits = int(''.join(map(str, digits)))\r
- if sign:\r
- digits = -digits\r
- if exp >= 0:\r
- return cls(digits * 10 ** exp)\r
- else:\r
- return cls(digits, 10 ** -exp)\r
-\r
- def limit_denominator(self, max_denominator=1000000):\r
- """Closest Fraction to self with denominator at most max_denominator.\r
-\r
- >>> Fraction('3.141592653589793').limit_denominator(10)\r
- Fraction(22, 7)\r
- >>> Fraction('3.141592653589793').limit_denominator(100)\r
- Fraction(311, 99)\r
- >>> Fraction(4321, 8765).limit_denominator(10000)\r
- Fraction(4321, 8765)\r
-\r
- """\r
- # Algorithm notes: For any real number x, define a *best upper\r
- # approximation* to x to be a rational number p/q such that:\r
- #\r
- # (1) p/q >= x, and\r
- # (2) if p/q > r/s >= x then s > q, for any rational r/s.\r
- #\r
- # Define *best lower approximation* similarly. Then it can be\r
- # proved that a rational number is a best upper or lower\r
- # approximation to x if, and only if, it is a convergent or\r
- # semiconvergent of the (unique shortest) continued fraction\r
- # associated to x.\r
- #\r
- # To find a best rational approximation with denominator <= M,\r
- # we find the best upper and lower approximations with\r
- # denominator <= M and take whichever of these is closer to x.\r
- # In the event of a tie, the bound with smaller denominator is\r
- # chosen. If both denominators are equal (which can happen\r
- # only when max_denominator == 1 and self is midway between\r
- # two integers) the lower bound---i.e., the floor of self, is\r
- # taken.\r
-\r
- if max_denominator < 1:\r
- raise ValueError("max_denominator should be at least 1")\r
- if self._denominator <= max_denominator:\r
- return Fraction(self)\r
-\r
- p0, q0, p1, q1 = 0, 1, 1, 0\r
- n, d = self._numerator, self._denominator\r
- while True:\r
- a = n//d\r
- q2 = q0+a*q1\r
- if q2 > max_denominator:\r
- break\r
- p0, q0, p1, q1 = p1, q1, p0+a*p1, q2\r
- n, d = d, n-a*d\r
-\r
- k = (max_denominator-q0)//q1\r
- bound1 = Fraction(p0+k*p1, q0+k*q1)\r
- bound2 = Fraction(p1, q1)\r
- if abs(bound2 - self) <= abs(bound1-self):\r
- return bound2\r
- else:\r
- return bound1\r
-\r
- @property\r
- def numerator(a):\r
- return a._numerator\r
-\r
- @property\r
- def denominator(a):\r
- return a._denominator\r
-\r
- def __repr__(self):\r
- """repr(self)"""\r
- return ('Fraction(%s, %s)' % (self._numerator, self._denominator))\r
-\r
- def __str__(self):\r
- """str(self)"""\r
- if self._denominator == 1:\r
- return str(self._numerator)\r
- else:\r
- return '%s/%s' % (self._numerator, self._denominator)\r
-\r
- def _operator_fallbacks(monomorphic_operator, fallback_operator):\r
- """Generates forward and reverse operators given a purely-rational\r
- operator and a function from the operator module.\r
-\r
- Use this like:\r
- __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op)\r
-\r
- In general, we want to implement the arithmetic operations so\r
- that mixed-mode operations either call an implementation whose\r
- author knew about the types of both arguments, or convert both\r
- to the nearest built in type and do the operation there. In\r
- Fraction, that means that we define __add__ and __radd__ as:\r
-\r
- def __add__(self, other):\r
- # Both types have numerators/denominator attributes,\r
- # so do the operation directly\r
- if isinstance(other, (int, long, Fraction)):\r
- return Fraction(self.numerator * other.denominator +\r
- other.numerator * self.denominator,\r
- self.denominator * other.denominator)\r
- # float and complex don't have those operations, but we\r
- # know about those types, so special case them.\r
- elif isinstance(other, float):\r
- return float(self) + other\r
- elif isinstance(other, complex):\r
- return complex(self) + other\r
- # Let the other type take over.\r
- return NotImplemented\r
-\r
- def __radd__(self, other):\r
- # radd handles more types than add because there's\r
- # nothing left to fall back to.\r
- if isinstance(other, Rational):\r
- return Fraction(self.numerator * other.denominator +\r
- other.numerator * self.denominator,\r
- self.denominator * other.denominator)\r
- elif isinstance(other, Real):\r
- return float(other) + float(self)\r
- elif isinstance(other, Complex):\r
- return complex(other) + complex(self)\r
- return NotImplemented\r
-\r
-\r
- There are 5 different cases for a mixed-type addition on\r
- Fraction. I'll refer to all of the above code that doesn't\r
- refer to Fraction, float, or complex as "boilerplate". 'r'\r
- will be an instance of Fraction, which is a subtype of\r
- Rational (r : Fraction <: Rational), and b : B <:\r
- Complex. The first three involve 'r + b':\r
-\r
- 1. If B <: Fraction, int, float, or complex, we handle\r
- that specially, and all is well.\r
- 2. If Fraction falls back to the boilerplate code, and it\r
- were to return a value from __add__, we'd miss the\r
- possibility that B defines a more intelligent __radd__,\r
- so the boilerplate should return NotImplemented from\r
- __add__. In particular, we don't handle Rational\r
- here, even though we could get an exact answer, in case\r
- the other type wants to do something special.\r
- 3. If B <: Fraction, Python tries B.__radd__ before\r
- Fraction.__add__. This is ok, because it was\r
- implemented with knowledge of Fraction, so it can\r
- handle those instances before delegating to Real or\r
- Complex.\r
-\r
- The next two situations describe 'b + r'. We assume that b\r
- didn't know about Fraction in its implementation, and that it\r
- uses similar boilerplate code:\r
-\r
- 4. If B <: Rational, then __radd_ converts both to the\r
- builtin rational type (hey look, that's us) and\r
- proceeds.\r
- 5. Otherwise, __radd__ tries to find the nearest common\r
- base ABC, and fall back to its builtin type. Since this\r
- class doesn't subclass a concrete type, there's no\r
- implementation to fall back to, so we need to try as\r
- hard as possible to return an actual value, or the user\r
- will get a TypeError.\r
-\r
- """\r
- def forward(a, b):\r
- if isinstance(b, (int, long, Fraction)):\r
- return monomorphic_operator(a, b)\r
- elif isinstance(b, float):\r
- return fallback_operator(float(a), b)\r
- elif isinstance(b, complex):\r
- return fallback_operator(complex(a), b)\r
- else:\r
- return NotImplemented\r
- forward.__name__ = '__' + fallback_operator.__name__ + '__'\r
- forward.__doc__ = monomorphic_operator.__doc__\r
-\r
- def reverse(b, a):\r
- if isinstance(a, Rational):\r
- # Includes ints.\r
- return monomorphic_operator(a, b)\r
- elif isinstance(a, numbers.Real):\r
- return fallback_operator(float(a), float(b))\r
- elif isinstance(a, numbers.Complex):\r
- return fallback_operator(complex(a), complex(b))\r
- else:\r
- return NotImplemented\r
- reverse.__name__ = '__r' + fallback_operator.__name__ + '__'\r
- reverse.__doc__ = monomorphic_operator.__doc__\r
-\r
- return forward, reverse\r
-\r
- def _add(a, b):\r
- """a + b"""\r
- return Fraction(a.numerator * b.denominator +\r
- b.numerator * a.denominator,\r
- a.denominator * b.denominator)\r
-\r
- __add__, __radd__ = _operator_fallbacks(_add, operator.add)\r
-\r
- def _sub(a, b):\r
- """a - b"""\r
- return Fraction(a.numerator * b.denominator -\r
- b.numerator * a.denominator,\r
- a.denominator * b.denominator)\r
-\r
- __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)\r
-\r
- def _mul(a, b):\r
- """a * b"""\r
- return Fraction(a.numerator * b.numerator, a.denominator * b.denominator)\r
-\r
- __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul)\r
-\r
- def _div(a, b):\r
- """a / b"""\r
- return Fraction(a.numerator * b.denominator,\r
- a.denominator * b.numerator)\r
-\r
- __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv)\r
- __div__, __rdiv__ = _operator_fallbacks(_div, operator.div)\r
-\r
- def __floordiv__(a, b):\r
- """a // b"""\r
- # Will be math.floor(a / b) in 3.0.\r
- div = a / b\r
- if isinstance(div, Rational):\r
- # trunc(math.floor(div)) doesn't work if the rational is\r
- # more precise than a float because the intermediate\r
- # rounding may cross an integer boundary.\r
- return div.numerator // div.denominator\r
- else:\r
- return math.floor(div)\r
-\r
- def __rfloordiv__(b, a):\r
- """a // b"""\r
- # Will be math.floor(a / b) in 3.0.\r
- div = a / b\r
- if isinstance(div, Rational):\r
- # trunc(math.floor(div)) doesn't work if the rational is\r
- # more precise than a float because the intermediate\r
- # rounding may cross an integer boundary.\r
- return div.numerator // div.denominator\r
- else:\r
- return math.floor(div)\r
-\r
- def __mod__(a, b):\r
- """a % b"""\r
- div = a // b\r
- return a - b * div\r
-\r
- def __rmod__(b, a):\r
- """a % b"""\r
- div = a // b\r
- return a - b * div\r
-\r
- def __pow__(a, b):\r
- """a ** b\r
-\r
- If b is not an integer, the result will be a float or complex\r
- since roots are generally irrational. If b is an integer, the\r
- result will be rational.\r
-\r
- """\r
- if isinstance(b, Rational):\r
- if b.denominator == 1:\r
- power = b.numerator\r
- if power >= 0:\r
- return Fraction(a._numerator ** power,\r
- a._denominator ** power)\r
- else:\r
- return Fraction(a._denominator ** -power,\r
- a._numerator ** -power)\r
- else:\r
- # A fractional power will generally produce an\r
- # irrational number.\r
- return float(a) ** float(b)\r
- else:\r
- return float(a) ** b\r
-\r
- def __rpow__(b, a):\r
- """a ** b"""\r
- if b._denominator == 1 and b._numerator >= 0:\r
- # If a is an int, keep it that way if possible.\r
- return a ** b._numerator\r
-\r
- if isinstance(a, Rational):\r
- return Fraction(a.numerator, a.denominator) ** b\r
-\r
- if b._denominator == 1:\r
- return a ** b._numerator\r
-\r
- return a ** float(b)\r
-\r
- def __pos__(a):\r
- """+a: Coerces a subclass instance to Fraction"""\r
- return Fraction(a._numerator, a._denominator)\r
-\r
- def __neg__(a):\r
- """-a"""\r
- return Fraction(-a._numerator, a._denominator)\r
-\r
- def __abs__(a):\r
- """abs(a)"""\r
- return Fraction(abs(a._numerator), a._denominator)\r
-\r
- def __trunc__(a):\r
- """trunc(a)"""\r
- if a._numerator < 0:\r
- return -(-a._numerator // a._denominator)\r
- else:\r
- return a._numerator // a._denominator\r
-\r
- def __hash__(self):\r
- """hash(self)\r
-\r
- Tricky because values that are exactly representable as a\r
- float must have the same hash as that float.\r
-\r
- """\r
- # XXX since this method is expensive, consider caching the result\r
- if self._denominator == 1:\r
- # Get integers right.\r
- return hash(self._numerator)\r
- # Expensive check, but definitely correct.\r
- if self == float(self):\r
- return hash(float(self))\r
- else:\r
- # Use tuple's hash to avoid a high collision rate on\r
- # simple fractions.\r
- return hash((self._numerator, self._denominator))\r
-\r
- def __eq__(a, b):\r
- """a == b"""\r
- if isinstance(b, Rational):\r
- return (a._numerator == b.numerator and\r
- a._denominator == b.denominator)\r
- if isinstance(b, numbers.Complex) and b.imag == 0:\r
- b = b.real\r
- if isinstance(b, float):\r
- if math.isnan(b) or math.isinf(b):\r
- # comparisons with an infinity or nan should behave in\r
- # the same way for any finite a, so treat a as zero.\r
- return 0.0 == b\r
- else:\r
- return a == a.from_float(b)\r
- else:\r
- # Since a doesn't know how to compare with b, let's give b\r
- # a chance to compare itself with a.\r
- return NotImplemented\r
-\r
- def _richcmp(self, other, op):\r
- """Helper for comparison operators, for internal use only.\r
-\r
- Implement comparison between a Rational instance `self`, and\r
- either another Rational instance or a float `other`. If\r
- `other` is not a Rational instance or a float, return\r
- NotImplemented. `op` should be one of the six standard\r
- comparison operators.\r
-\r
- """\r
- # convert other to a Rational instance where reasonable.\r
- if isinstance(other, Rational):\r
- return op(self._numerator * other.denominator,\r
- self._denominator * other.numerator)\r
- # comparisons with complex should raise a TypeError, for consistency\r
- # with int<->complex, float<->complex, and complex<->complex comparisons.\r
- if isinstance(other, complex):\r
- raise TypeError("no ordering relation is defined for complex numbers")\r
- if isinstance(other, float):\r
- if math.isnan(other) or math.isinf(other):\r
- return op(0.0, other)\r
- else:\r
- return op(self, self.from_float(other))\r
- else:\r
- return NotImplemented\r
-\r
- def __lt__(a, b):\r
- """a < b"""\r
- return a._richcmp(b, operator.lt)\r
-\r
- def __gt__(a, b):\r
- """a > b"""\r
- return a._richcmp(b, operator.gt)\r
-\r
- def __le__(a, b):\r
- """a <= b"""\r
- return a._richcmp(b, operator.le)\r
-\r
- def __ge__(a, b):\r
- """a >= b"""\r
- return a._richcmp(b, operator.ge)\r
-\r
- def __nonzero__(a):\r
- """a != 0"""\r
- return a._numerator != 0\r
-\r
- # support for pickling, copy, and deepcopy\r
-\r
- def __reduce__(self):\r
- return (self.__class__, (str(self),))\r
-\r
- def __copy__(self):\r
- if type(self) == Fraction:\r
- return self # I'm immutable; therefore I am my own clone\r
- return self.__class__(self._numerator, self._denominator)\r
-\r
- def __deepcopy__(self, memo):\r
- if type(self) == Fraction:\r
- return self # My components are also immutable\r
- return self.__class__(self._numerator, self._denominator)\r
projects / mirror_edk2.git / blobdiff