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