home *** CD-ROM | disk | FTP | other *** search
/ Chip 2011 November / CHIP_2011_11.iso / Programy / Narzedzia / Inkscape / Inkscape-0.48.2-1-win32.exe / python / Lib / fractions.py < prev    next >
Encoding:
Python Source  |  2010-05-29  |  20.1 KB  |  540 lines
  1. # Originally contributed by Sjoerd Mullender.
  2. # Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>.
  3.  
  4. """Rational, infinite-precision, real numbers."""
  5.  
  6. from __future__ import division
  7. import math
  8. import numbers
  9. import operator
  10. import re
  11.  
  12. __all__ = ['Fraction', 'gcd']
  13.  
  14. Rational = numbers.Rational
  15.  
  16.  
  17. def gcd(a, b):
  18.     """Calculate the Greatest Common Divisor of a and b.
  19.  
  20.     Unless b==0, the result will have the same sign as b (so that when
  21.     b is divided by it, the result comes out positive).
  22.     """
  23.     while b:
  24.         a, b = b, a%b
  25.     return a
  26.  
  27.  
  28. _RATIONAL_FORMAT = re.compile(r"""
  29.     \A\s*                      # optional whitespace at the start, then
  30.     (?P<sign>[-+]?)            # an optional sign, then
  31.     (?=\d|\.\d)                # lookahead for digit or .digit
  32.     (?P<num>\d*)               # numerator (possibly empty)
  33.     (?:                        # followed by an optional
  34.        /(?P<denom>\d+)         # / and denominator
  35.     |                          # or
  36.        \.(?P<decimal>\d*)      # decimal point and fractional part
  37.     )?
  38.     \s*\Z                      # and optional whitespace to finish
  39. """, re.VERBOSE)
  40.  
  41.  
  42. class Fraction(Rational):
  43.     """This class implements rational numbers.
  44.  
  45.     Fraction(8, 6) will produce a rational number equivalent to
  46.     4/3. Both arguments must be Integral. The numerator defaults to 0
  47.     and the denominator defaults to 1 so that Fraction(3) == 3 and
  48.     Fraction() == 0.
  49.  
  50.     Fractions can also be constructed from strings of the form
  51.     '[-+]?[0-9]+((/|.)[0-9]+)?', optionally surrounded by spaces.
  52.  
  53.     """
  54.  
  55.     __slots__ = ('_numerator', '_denominator')
  56.  
  57.     # We're immutable, so use __new__ not __init__
  58.     def __new__(cls, numerator=0, denominator=1):
  59.         """Constructs a Fraction.
  60.  
  61.         Takes a string like '3/2' or '1.5', another Fraction, or a
  62.         numerator/denominator pair.
  63.  
  64.         """
  65.         self = super(Fraction, cls).__new__(cls)
  66.  
  67.         if type(numerator) not in (int, long) and denominator == 1:
  68.             if isinstance(numerator, basestring):
  69.                 # Handle construction from strings.
  70.                 input = numerator
  71.                 m = _RATIONAL_FORMAT.match(input)
  72.                 if m is None:
  73.                     raise ValueError('Invalid literal for Fraction: %r' % input)
  74.                 numerator = m.group('num')
  75.                 decimal = m.group('decimal')
  76.                 if decimal:
  77.                     # The literal is a decimal number.
  78.                     numerator = int(numerator + decimal)
  79.                     denominator = 10**len(decimal)
  80.                 else:
  81.                     # The literal is an integer or fraction.
  82.                     numerator = int(numerator)
  83.                     # Default denominator to 1.
  84.                     denominator = int(m.group('denom') or 1)
  85.  
  86.                 if m.group('sign') == '-':
  87.                     numerator = -numerator
  88.  
  89.             elif isinstance(numerator, Rational):
  90.                 # Handle copies from other rationals. Integrals get
  91.                 # caught here too, but it doesn't matter because
  92.                 # denominator is already 1.
  93.                 other_rational = numerator
  94.                 numerator = other_rational.numerator
  95.                 denominator = other_rational.denominator
  96.  
  97.         if denominator == 0:
  98.             raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
  99.         numerator = operator.index(numerator)
  100.         denominator = operator.index(denominator)
  101.         g = gcd(numerator, denominator)
  102.         self._numerator = numerator // g
  103.         self._denominator = denominator // g
  104.         return self
  105.  
  106.     @classmethod
  107.     def from_float(cls, f):
  108.         """Converts a finite float to a rational number, exactly.
  109.  
  110.         Beware that Fraction.from_float(0.3) != Fraction(3, 10).
  111.  
  112.         """
  113.         if isinstance(f, numbers.Integral):
  114.             return cls(f)
  115.         elif not isinstance(f, float):
  116.             raise TypeError("%s.from_float() only takes floats, not %r (%s)" %
  117.                             (cls.__name__, f, type(f).__name__))
  118.         if math.isnan(f) or math.isinf(f):
  119.             raise TypeError("Cannot convert %r to %s." % (f, cls.__name__))
  120.         return cls(*f.as_integer_ratio())
  121.  
  122.     @classmethod
  123.     def from_decimal(cls, dec):
  124.         """Converts a finite Decimal instance to a rational number, exactly."""
  125.         from decimal import Decimal
  126.         if isinstance(dec, numbers.Integral):
  127.             dec = Decimal(int(dec))
  128.         elif not isinstance(dec, Decimal):
  129.             raise TypeError(
  130.                 "%s.from_decimal() only takes Decimals, not %r (%s)" %
  131.                 (cls.__name__, dec, type(dec).__name__))
  132.         if not dec.is_finite():
  133.             # Catches infinities and nans.
  134.             raise TypeError("Cannot convert %s to %s." % (dec, cls.__name__))
  135.         sign, digits, exp = dec.as_tuple()
  136.         digits = int(''.join(map(str, digits)))
  137.         if sign:
  138.             digits = -digits
  139.         if exp >= 0:
  140.             return cls(digits * 10 ** exp)
  141.         else:
  142.             return cls(digits, 10 ** -exp)
  143.  
  144.     def limit_denominator(self, max_denominator=1000000):
  145.         """Closest Fraction to self with denominator at most max_denominator.
  146.  
  147.         >>> Fraction('3.141592653589793').limit_denominator(10)
  148.         Fraction(22, 7)
  149.         >>> Fraction('3.141592653589793').limit_denominator(100)
  150.         Fraction(311, 99)
  151.         >>> Fraction(4321, 8765).limit_denominator(10000)
  152.         Fraction(4321, 8765)
  153.  
  154.         """
  155.         # Algorithm notes: For any real number x, define a *best upper
  156.         # approximation* to x to be a rational number p/q such that:
  157.         #
  158.         #   (1) p/q >= x, and
  159.         #   (2) if p/q > r/s >= x then s > q, for any rational r/s.
  160.         #
  161.         # Define *best lower approximation* similarly.  Then it can be
  162.         # proved that a rational number is a best upper or lower
  163.         # approximation to x if, and only if, it is a convergent or
  164.         # semiconvergent of the (unique shortest) continued fraction
  165.         # associated to x.
  166.         #
  167.         # To find a best rational approximation with denominator <= M,
  168.         # we find the best upper and lower approximations with
  169.         # denominator <= M and take whichever of these is closer to x.
  170.         # In the event of a tie, the bound with smaller denominator is
  171.         # chosen.  If both denominators are equal (which can happen
  172.         # only when max_denominator == 1 and self is midway between
  173.         # two integers) the lower bound---i.e., the floor of self, is
  174.         # taken.
  175.  
  176.         if max_denominator < 1:
  177.             raise ValueError("max_denominator should be at least 1")
  178.         if self._denominator <= max_denominator:
  179.             return Fraction(self)
  180.  
  181.         p0, q0, p1, q1 = 0, 1, 1, 0
  182.         n, d = self._numerator, self._denominator
  183.         while True:
  184.             a = n//d
  185.             q2 = q0+a*q1
  186.             if q2 > max_denominator:
  187.                 break
  188.             p0, q0, p1, q1 = p1, q1, p0+a*p1, q2
  189.             n, d = d, n-a*d
  190.  
  191.         k = (max_denominator-q0)//q1
  192.         bound1 = Fraction(p0+k*p1, q0+k*q1)
  193.         bound2 = Fraction(p1, q1)
  194.         if abs(bound2 - self) <= abs(bound1-self):
  195.             return bound2
  196.         else:
  197.             return bound1
  198.  
  199.     @property
  200.     def numerator(a):
  201.         return a._numerator
  202.  
  203.     @property
  204.     def denominator(a):
  205.         return a._denominator
  206.  
  207.     def __repr__(self):
  208.         """repr(self)"""
  209.         return ('Fraction(%s, %s)' % (self._numerator, self._denominator))
  210.  
  211.     def __str__(self):
  212.         """str(self)"""
  213.         if self._denominator == 1:
  214.             return str(self._numerator)
  215.         else:
  216.             return '%s/%s' % (self._numerator, self._denominator)
  217.  
  218.     def _operator_fallbacks(monomorphic_operator, fallback_operator):
  219.         """Generates forward and reverse operators given a purely-rational
  220.         operator and a function from the operator module.
  221.  
  222.         Use this like:
  223.         __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op)
  224.  
  225.         In general, we want to implement the arithmetic operations so
  226.         that mixed-mode operations either call an implementation whose
  227.         author knew about the types of both arguments, or convert both
  228.         to the nearest built in type and do the operation there. In
  229.         Fraction, that means that we define __add__ and __radd__ as:
  230.  
  231.             def __add__(self, other):
  232.                 # Both types have numerators/denominator attributes,
  233.                 # so do the operation directly
  234.                 if isinstance(other, (int, long, Fraction)):
  235.                     return Fraction(self.numerator * other.denominator +
  236.                                     other.numerator * self.denominator,
  237.                                     self.denominator * other.denominator)
  238.                 # float and complex don't have those operations, but we
  239.                 # know about those types, so special case them.
  240.                 elif isinstance(other, float):
  241.                     return float(self) + other
  242.                 elif isinstance(other, complex):
  243.                     return complex(self) + other
  244.                 # Let the other type take over.
  245.                 return NotImplemented
  246.  
  247.             def __radd__(self, other):
  248.                 # radd handles more types than add because there's
  249.                 # nothing left to fall back to.
  250.                 if isinstance(other, Rational):
  251.                     return Fraction(self.numerator * other.denominator +
  252.                                     other.numerator * self.denominator,
  253.                                     self.denominator * other.denominator)
  254.                 elif isinstance(other, Real):
  255.                     return float(other) + float(self)
  256.                 elif isinstance(other, Complex):
  257.                     return complex(other) + complex(self)
  258.                 return NotImplemented
  259.  
  260.  
  261.         There are 5 different cases for a mixed-type addition on
  262.         Fraction. I'll refer to all of the above code that doesn't
  263.         refer to Fraction, float, or complex as "boilerplate". 'r'
  264.         will be an instance of Fraction, which is a subtype of
  265.         Rational (r : Fraction <: Rational), and b : B <:
  266.         Complex. The first three involve 'r + b':
  267.  
  268.             1. If B <: Fraction, int, float, or complex, we handle
  269.                that specially, and all is well.
  270.             2. If Fraction falls back to the boilerplate code, and it
  271.                were to return a value from __add__, we'd miss the
  272.                possibility that B defines a more intelligent __radd__,
  273.                so the boilerplate should return NotImplemented from
  274.                __add__. In particular, we don't handle Rational
  275.                here, even though we could get an exact answer, in case
  276.                the other type wants to do something special.
  277.             3. If B <: Fraction, Python tries B.__radd__ before
  278.                Fraction.__add__. This is ok, because it was
  279.                implemented with knowledge of Fraction, so it can
  280.                handle those instances before delegating to Real or
  281.                Complex.
  282.  
  283.         The next two situations describe 'b + r'. We assume that b
  284.         didn't know about Fraction in its implementation, and that it
  285.         uses similar boilerplate code:
  286.  
  287.             4. If B <: Rational, then __radd_ converts both to the
  288.                builtin rational type (hey look, that's us) and
  289.                proceeds.
  290.             5. Otherwise, __radd__ tries to find the nearest common
  291.                base ABC, and fall back to its builtin type. Since this
  292.                class doesn't subclass a concrete type, there's no
  293.                implementation to fall back to, so we need to try as
  294.                hard as possible to return an actual value, or the user
  295.                will get a TypeError.
  296.  
  297.         """
  298.         def forward(a, b):
  299.             if isinstance(b, (int, long, Fraction)):
  300.                 return monomorphic_operator(a, b)
  301.             elif isinstance(b, float):
  302.                 return fallback_operator(float(a), b)
  303.             elif isinstance(b, complex):
  304.                 return fallback_operator(complex(a), b)
  305.             else:
  306.                 return NotImplemented
  307.         forward.__name__ = '__' + fallback_operator.__name__ + '__'
  308.         forward.__doc__ = monomorphic_operator.__doc__
  309.  
  310.         def reverse(b, a):
  311.             if isinstance(a, Rational):
  312.                 # Includes ints.
  313.                 return monomorphic_operator(a, b)
  314.             elif isinstance(a, numbers.Real):
  315.                 return fallback_operator(float(a), float(b))
  316.             elif isinstance(a, numbers.Complex):
  317.                 return fallback_operator(complex(a), complex(b))
  318.             else:
  319.                 return NotImplemented
  320.         reverse.__name__ = '__r' + fallback_operator.__name__ + '__'
  321.         reverse.__doc__ = monomorphic_operator.__doc__
  322.  
  323.         return forward, reverse
  324.  
  325.     def _add(a, b):
  326.         """a + b"""
  327.         return Fraction(a.numerator * b.denominator +
  328.                         b.numerator * a.denominator,
  329.                         a.denominator * b.denominator)
  330.  
  331.     __add__, __radd__ = _operator_fallbacks(_add, operator.add)
  332.  
  333.     def _sub(a, b):
  334.         """a - b"""
  335.         return Fraction(a.numerator * b.denominator -
  336.                         b.numerator * a.denominator,
  337.                         a.denominator * b.denominator)
  338.  
  339.     __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)
  340.  
  341.     def _mul(a, b):
  342.         """a * b"""
  343.         return Fraction(a.numerator * b.numerator, a.denominator * b.denominator)
  344.  
  345.     __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul)
  346.  
  347.     def _div(a, b):
  348.         """a / b"""
  349.         return Fraction(a.numerator * b.denominator,
  350.                         a.denominator * b.numerator)
  351.  
  352.     __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv)
  353.     __div__, __rdiv__ = _operator_fallbacks(_div, operator.div)
  354.  
  355.     def __floordiv__(a, b):
  356.         """a // b"""
  357.         # Will be math.floor(a / b) in 3.0.
  358.         div = a / b
  359.         if isinstance(div, Rational):
  360.             # trunc(math.floor(div)) doesn't work if the rational is
  361.             # more precise than a float because the intermediate
  362.             # rounding may cross an integer boundary.
  363.             return div.numerator // div.denominator
  364.         else:
  365.             return math.floor(div)
  366.  
  367.     def __rfloordiv__(b, a):
  368.         """a // b"""
  369.         # Will be math.floor(a / b) in 3.0.
  370.         div = a / b
  371.         if isinstance(div, Rational):
  372.             # trunc(math.floor(div)) doesn't work if the rational is
  373.             # more precise than a float because the intermediate
  374.             # rounding may cross an integer boundary.
  375.             return div.numerator // div.denominator
  376.         else:
  377.             return math.floor(div)
  378.  
  379.     def __mod__(a, b):
  380.         """a % b"""
  381.         div = a // b
  382.         return a - b * div
  383.  
  384.     def __rmod__(b, a):
  385.         """a % b"""
  386.         div = a // b
  387.         return a - b * div
  388.  
  389.     def __pow__(a, b):
  390.         """a ** b
  391.  
  392.         If b is not an integer, the result will be a float or complex
  393.         since roots are generally irrational. If b is an integer, the
  394.         result will be rational.
  395.  
  396.         """
  397.         if isinstance(b, Rational):
  398.             if b.denominator == 1:
  399.                 power = b.numerator
  400.                 if power >= 0:
  401.                     return Fraction(a._numerator ** power,
  402.                                     a._denominator ** power)
  403.                 else:
  404.                     return Fraction(a._denominator ** -power,
  405.                                     a._numerator ** -power)
  406.             else:
  407.                 # A fractional power will generally produce an
  408.                 # irrational number.
  409.                 return float(a) ** float(b)
  410.         else:
  411.             return float(a) ** b
  412.  
  413.     def __rpow__(b, a):
  414.         """a ** b"""
  415.         if b._denominator == 1 and b._numerator >= 0:
  416.             # If a is an int, keep it that way if possible.
  417.             return a ** b._numerator
  418.  
  419.         if isinstance(a, Rational):
  420.             return Fraction(a.numerator, a.denominator) ** b
  421.  
  422.         if b._denominator == 1:
  423.             return a ** b._numerator
  424.  
  425.         return a ** float(b)
  426.  
  427.     def __pos__(a):
  428.         """+a: Coerces a subclass instance to Fraction"""
  429.         return Fraction(a._numerator, a._denominator)
  430.  
  431.     def __neg__(a):
  432.         """-a"""
  433.         return Fraction(-a._numerator, a._denominator)
  434.  
  435.     def __abs__(a):
  436.         """abs(a)"""
  437.         return Fraction(abs(a._numerator), a._denominator)
  438.  
  439.     def __trunc__(a):
  440.         """trunc(a)"""
  441.         if a._numerator < 0:
  442.             return -(-a._numerator // a._denominator)
  443.         else:
  444.             return a._numerator // a._denominator
  445.  
  446.     def __hash__(self):
  447.         """hash(self)
  448.  
  449.         Tricky because values that are exactly representable as a
  450.         float must have the same hash as that float.
  451.  
  452.         """
  453.         # XXX since this method is expensive, consider caching the result
  454.         if self._denominator == 1:
  455.             # Get integers right.
  456.             return hash(self._numerator)
  457.         # Expensive check, but definitely correct.
  458.         if self == float(self):
  459.             return hash(float(self))
  460.         else:
  461.             # Use tuple's hash to avoid a high collision rate on
  462.             # simple fractions.
  463.             return hash((self._numerator, self._denominator))
  464.  
  465.     def __eq__(a, b):
  466.         """a == b"""
  467.         if isinstance(b, Rational):
  468.             return (a._numerator == b.numerator and
  469.                     a._denominator == b.denominator)
  470.         if isinstance(b, numbers.Complex) and b.imag == 0:
  471.             b = b.real
  472.         if isinstance(b, float):
  473.             return a == a.from_float(b)
  474.         else:
  475.             # XXX: If b.__eq__ is implemented like this method, it may
  476.             # give the wrong answer after float(a) changes a's
  477.             # value. Better ways of doing this are welcome.
  478.             return float(a) == b
  479.  
  480.     def _subtractAndCompareToZero(a, b, op):
  481.         """Helper function for comparison operators.
  482.  
  483.         Subtracts b from a, exactly if possible, and compares the
  484.         result with 0 using op, in such a way that the comparison
  485.         won't recurse. If the difference raises a TypeError, returns
  486.         NotImplemented instead.
  487.  
  488.         """
  489.         if isinstance(b, numbers.Complex) and b.imag == 0:
  490.             b = b.real
  491.         if isinstance(b, float):
  492.             b = a.from_float(b)
  493.         try:
  494.             # XXX: If b <: Real but not <: Rational, this is likely
  495.             # to fall back to a float. If the actual values differ by
  496.             # less than MIN_FLOAT, this could falsely call them equal,
  497.             # which would make <= inconsistent with ==. Better ways of
  498.             # doing this are welcome.
  499.             diff = a - b
  500.         except TypeError:
  501.             return NotImplemented
  502.         if isinstance(diff, Rational):
  503.             return op(diff.numerator, 0)
  504.         return op(diff, 0)
  505.  
  506.     def __lt__(a, b):
  507.         """a < b"""
  508.         return a._subtractAndCompareToZero(b, operator.lt)
  509.  
  510.     def __gt__(a, b):
  511.         """a > b"""
  512.         return a._subtractAndCompareToZero(b, operator.gt)
  513.  
  514.     def __le__(a, b):
  515.         """a <= b"""
  516.         return a._subtractAndCompareToZero(b, operator.le)
  517.  
  518.     def __ge__(a, b):
  519.         """a >= b"""
  520.         return a._subtractAndCompareToZero(b, operator.ge)
  521.  
  522.     def __nonzero__(a):
  523.         """a != 0"""
  524.         return a._numerator != 0
  525.  
  526.     # support for pickling, copy, and deepcopy
  527.  
  528.     def __reduce__(self):
  529.         return (self.__class__, (str(self),))
  530.  
  531.     def __copy__(self):
  532.         if type(self) == Fraction:
  533.             return self     # I'm immutable; therefore I am my own clone
  534.         return self.__class__(self._numerator, self._denominator)
  535.  
  536.     def __deepcopy__(self, memo):
  537.         if type(self) == Fraction:
  538.             return self     # My components are also immutable
  539.         return self.__class__(self._numerator, self._denominator)
  540.