Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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 |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 10 | import re |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 11 | |
Raymond Hettinger | cf98f03 | 2008-05-08 04:36:12 +0000 | [diff] [blame] | 12 | __all__ = ['Fraction', 'gcd'] |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 13 | |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 14 | Rational = numbers.Rational |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 15 | |
| 16 | |
Jeffrey Yasskin | 3e1a373 | 2008-01-27 05:40:35 +0000 | [diff] [blame] | 17 | def gcd(a, b): |
| 18 | """Calculate the Greatest Common Divisor of a and b. |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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 | |
Mark Dickinson | 1dabdb2 | 2008-02-02 17:16:13 +0000 | [diff] [blame] | 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) |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 40 | |
| 41 | |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 42 | class Fraction(Rational): |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 43 | """This class implements rational numbers. |
| 44 | |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 45 | Fraction(8, 6) will produce a rational number equivalent to |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 46 | 4/3. Both arguments must be Integral. The numerator defaults to 0 |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 47 | and the denominator defaults to 1 so that Fraction(3) == 3 and |
| 48 | Fraction() == 0. |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 49 | |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 50 | Fractions can also be constructed from strings of the form |
Jeffrey Yasskin | 3e1a373 | 2008-01-27 05:40:35 +0000 | [diff] [blame] | 51 | '[-+]?[0-9]+((/|.)[0-9]+)?', optionally surrounded by spaces. |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 52 | |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 53 | """ |
| 54 | |
Jeffrey Yasskin | dc2964b | 2008-02-01 07:05:46 +0000 | [diff] [blame] | 55 | __slots__ = ('_numerator', '_denominator') |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 56 | |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 57 | # We're immutable, so use __new__ not __init__ |
| 58 | def __new__(cls, numerator=0, denominator=1): |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 59 | """Constructs a Fraction. |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 60 | |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 61 | Takes a string like '3/2' or '1.5', another Fraction, or a |
Jeffrey Yasskin | 3e1a373 | 2008-01-27 05:40:35 +0000 | [diff] [blame] | 62 | numerator/denominator pair. |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 63 | |
| 64 | """ |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 65 | self = super(Fraction, cls).__new__(cls) |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 66 | |
Jeffrey Yasskin | 1c214d6 | 2008-02-14 06:12:24 +0000 | [diff] [blame] | 67 | if type(numerator) not in (int, long) and denominator == 1: |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 68 | if isinstance(numerator, basestring): |
| 69 | # Handle construction from strings. |
| 70 | input = numerator |
| 71 | m = _RATIONAL_FORMAT.match(input) |
| 72 | if m is None: |
Andrew M. Kuchling | f484363 | 2008-06-21 13:47:20 +0000 | [diff] [blame] | 73 | raise ValueError('Invalid literal for Fraction: %r' % input) |
Jeffrey Yasskin | 3e1a373 | 2008-01-27 05:40:35 +0000 | [diff] [blame] | 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 | |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 86 | if m.group('sign') == '-': |
| 87 | numerator = -numerator |
| 88 | |
Jeffrey Yasskin | 1c214d6 | 2008-02-14 06:12:24 +0000 | [diff] [blame] | 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. |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 93 | other_rational = numerator |
| 94 | numerator = other_rational.numerator |
| 95 | denominator = other_rational.denominator |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 96 | |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 97 | if denominator == 0: |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 98 | raise ZeroDivisionError('Fraction(%s, 0)' % numerator) |
Raymond Hettinger | 548db58 | 2008-07-10 10:28:41 +0000 | [diff] [blame] | 99 | numerator = operator.index(numerator) |
| 100 | denominator = operator.index(denominator) |
Jeffrey Yasskin | 3e1a373 | 2008-01-27 05:40:35 +0000 | [diff] [blame] | 101 | g = gcd(numerator, denominator) |
Jeffrey Yasskin | 1c214d6 | 2008-02-14 06:12:24 +0000 | [diff] [blame] | 102 | self._numerator = numerator // g |
| 103 | self._denominator = denominator // g |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 104 | return self |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 105 | |
Mark Dickinson | 0aa52a1 | 2008-02-12 21:40:53 +0000 | [diff] [blame] | 106 | @classmethod |
| 107 | def from_float(cls, f): |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 108 | """Converts a finite float to a rational number, exactly. |
| 109 | |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 110 | Beware that Fraction.from_float(0.3) != Fraction(3, 10). |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 111 | |
| 112 | """ |
Raymond Hettinger | b01713e | 2008-07-10 14:34:57 +0000 | [diff] [blame] | 113 | if isinstance(f, numbers.Integral): |
Georg Brandl | fe42789 | 2009-01-03 22:03:11 +0000 | [diff] [blame] | 114 | return cls(f) |
Raymond Hettinger | b01713e | 2008-07-10 14:34:57 +0000 | [diff] [blame] | 115 | elif not isinstance(f, float): |
Mark Dickinson | 0aa52a1 | 2008-02-12 21:40:53 +0000 | [diff] [blame] | 116 | raise TypeError("%s.from_float() only takes floats, not %r (%s)" % |
| 117 | (cls.__name__, f, type(f).__name__)) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 118 | if math.isnan(f) or math.isinf(f): |
Mark Dickinson | 0aa52a1 | 2008-02-12 21:40:53 +0000 | [diff] [blame] | 119 | raise TypeError("Cannot convert %r to %s." % (f, cls.__name__)) |
| 120 | return cls(*f.as_integer_ratio()) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 121 | |
Mark Dickinson | 0aa52a1 | 2008-02-12 21:40:53 +0000 | [diff] [blame] | 122 | @classmethod |
| 123 | def from_decimal(cls, dec): |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 124 | """Converts a finite Decimal instance to a rational number, exactly.""" |
| 125 | from decimal import Decimal |
Raymond Hettinger | b01713e | 2008-07-10 14:34:57 +0000 | [diff] [blame] | 126 | if isinstance(dec, numbers.Integral): |
| 127 | dec = Decimal(int(dec)) |
| 128 | elif not isinstance(dec, Decimal): |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 129 | raise TypeError( |
Mark Dickinson | 0aa52a1 | 2008-02-12 21:40:53 +0000 | [diff] [blame] | 130 | "%s.from_decimal() only takes Decimals, not %r (%s)" % |
| 131 | (cls.__name__, dec, type(dec).__name__)) |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 132 | if not dec.is_finite(): |
| 133 | # Catches infinities and nans. |
Mark Dickinson | 0aa52a1 | 2008-02-12 21:40:53 +0000 | [diff] [blame] | 134 | raise TypeError("Cannot convert %s to %s." % (dec, cls.__name__)) |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 135 | sign, digits, exp = dec.as_tuple() |
| 136 | digits = int(''.join(map(str, digits))) |
| 137 | if sign: |
| 138 | digits = -digits |
| 139 | if exp >= 0: |
Mark Dickinson | 0aa52a1 | 2008-02-12 21:40:53 +0000 | [diff] [blame] | 140 | return cls(digits * 10 ** exp) |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 141 | else: |
Mark Dickinson | 0aa52a1 | 2008-02-12 21:40:53 +0000 | [diff] [blame] | 142 | return cls(digits, 10 ** -exp) |
Jeffrey Yasskin | 45169fb | 2008-01-19 09:56:06 +0000 | [diff] [blame] | 143 | |
Mark Dickinson | e1b8247 | 2008-02-12 21:31:59 +0000 | [diff] [blame] | 144 | def limit_denominator(self, max_denominator=1000000): |
| 145 | """Closest Fraction to self with denominator at most max_denominator. |
Raymond Hettinger | cf10926 | 2008-01-24 00:54:21 +0000 | [diff] [blame] | 146 | |
Mark Dickinson | e1b8247 | 2008-02-12 21:31:59 +0000 | [diff] [blame] | 147 | >>> Fraction('3.141592653589793').limit_denominator(10) |
| 148 | Fraction(22, 7) |
| 149 | >>> Fraction('3.141592653589793').limit_denominator(100) |
| 150 | Fraction(311, 99) |
| 151 | >>> Fraction(1234, 5678).limit_denominator(10000) |
| 152 | Fraction(1234, 5678) |
Raymond Hettinger | cf10926 | 2008-01-24 00:54:21 +0000 | [diff] [blame] | 153 | |
Mark Dickinson | e1b8247 | 2008-02-12 21:31:59 +0000 | [diff] [blame] | 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") |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 178 | if self._denominator <= max_denominator: |
Mark Dickinson | e1b8247 | 2008-02-12 21:31:59 +0000 | [diff] [blame] | 179 | return Fraction(self) |
| 180 | |
| 181 | p0, q0, p1, q1 = 0, 1, 1, 0 |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 182 | n, d = self._numerator, self._denominator |
Mark Dickinson | e1b8247 | 2008-02-12 21:31:59 +0000 | [diff] [blame] | 183 | while True: |
| 184 | a = n//d |
| 185 | q2 = q0+a*q1 |
| 186 | if q2 > max_denominator: |
Raymond Hettinger | cf10926 | 2008-01-24 00:54:21 +0000 | [diff] [blame] | 187 | break |
Mark Dickinson | e1b8247 | 2008-02-12 21:31:59 +0000 | [diff] [blame] | 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 |
Raymond Hettinger | cf10926 | 2008-01-24 00:54:21 +0000 | [diff] [blame] | 198 | |
Jeffrey Yasskin | dc2964b | 2008-02-01 07:05:46 +0000 | [diff] [blame] | 199 | @property |
| 200 | def numerator(a): |
| 201 | return a._numerator |
| 202 | |
| 203 | @property |
| 204 | def denominator(a): |
| 205 | return a._denominator |
| 206 | |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 207 | def __repr__(self): |
| 208 | """repr(self)""" |
Mark Dickinson | 3af386a | 2008-06-27 10:11:52 +0000 | [diff] [blame] | 209 | return ('Fraction(%s, %s)' % (self._numerator, self._denominator)) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 210 | |
| 211 | def __str__(self): |
| 212 | """str(self)""" |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 213 | if self._denominator == 1: |
| 214 | return str(self._numerator) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 215 | else: |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 216 | return '%s/%s' % (self._numerator, self._denominator) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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 | |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 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 |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 229 | Fraction, that means that we define __add__ and __radd__ as: |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 230 | |
| 231 | def __add__(self, other): |
Raymond Hettinger | 2df20a3 | 2008-01-31 22:07:16 +0000 | [diff] [blame] | 232 | # Both types have numerators/denominator attributes, |
| 233 | # so do the operation directly |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 234 | if isinstance(other, (int, long, Fraction)): |
| 235 | return Fraction(self.numerator * other.denominator + |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 236 | other.numerator * self.denominator, |
| 237 | self.denominator * other.denominator) |
Raymond Hettinger | 2df20a3 | 2008-01-31 22:07:16 +0000 | [diff] [blame] | 238 | # float and complex don't have those operations, but we |
| 239 | # know about those types, so special case them. |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 240 | elif isinstance(other, float): |
| 241 | return float(self) + other |
| 242 | elif isinstance(other, complex): |
| 243 | return complex(self) + other |
Raymond Hettinger | 2df20a3 | 2008-01-31 22:07:16 +0000 | [diff] [blame] | 244 | # Let the other type take over. |
| 245 | return NotImplemented |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 246 | |
| 247 | def __radd__(self, other): |
| 248 | # radd handles more types than add because there's |
| 249 | # nothing left to fall back to. |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 250 | if isinstance(other, Rational): |
| 251 | return Fraction(self.numerator * other.denominator + |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 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) |
Raymond Hettinger | 2df20a3 | 2008-01-31 22:07:16 +0000 | [diff] [blame] | 258 | return NotImplemented |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 259 | |
| 260 | |
| 261 | There are 5 different cases for a mixed-type addition on |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 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 <: |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 266 | Complex. The first three involve 'r + b': |
| 267 | |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 268 | 1. If B <: Fraction, int, float, or complex, we handle |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 269 | that specially, and all is well. |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 270 | 2. If Fraction falls back to the boilerplate code, and it |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 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 |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 274 | __add__. In particular, we don't handle Rational |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 275 | here, even though we could get an exact answer, in case |
| 276 | the other type wants to do something special. |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 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 |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 280 | handle those instances before delegating to Real or |
| 281 | Complex. |
| 282 | |
| 283 | The next two situations describe 'b + r'. We assume that b |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 284 | didn't know about Fraction in its implementation, and that it |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 285 | uses similar boilerplate code: |
| 286 | |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 287 | 4. If B <: Rational, then __radd_ converts both to the |
Jeffrey Yasskin | b23dea6 | 2008-01-31 07:44:11 +0000 | [diff] [blame] | 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 | |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 297 | """ |
| 298 | def forward(a, b): |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 299 | if isinstance(b, (int, long, Fraction)): |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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): |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 311 | if isinstance(a, Rational): |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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""" |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 327 | return Fraction(a.numerator * b.denominator + |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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""" |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 335 | return Fraction(a.numerator * b.denominator - |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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""" |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 343 | return Fraction(a.numerator * b.numerator, a.denominator * b.denominator) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 344 | |
| 345 | __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul) |
| 346 | |
| 347 | def _div(a, b): |
| 348 | """a / b""" |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 349 | return Fraction(a.numerator * b.denominator, |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 350 | a.denominator * b.numerator) |
| 351 | |
| 352 | __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv) |
| 353 | __div__, __rdiv__ = _operator_fallbacks(_div, operator.div) |
| 354 | |
Raymond Hettinger | 909e334 | 2008-01-24 23:50:26 +0000 | [diff] [blame] | 355 | def __floordiv__(a, b): |
| 356 | """a // b""" |
| 357 | # Will be math.floor(a / b) in 3.0. |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 358 | div = a / b |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 359 | if isinstance(div, Rational): |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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 | |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 367 | def __rfloordiv__(b, a): |
| 368 | """a // b""" |
| 369 | # Will be math.floor(a / b) in 3.0. |
Raymond Hettinger | 909e334 | 2008-01-24 23:50:26 +0000 | [diff] [blame] | 370 | div = a / b |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 371 | if isinstance(div, Rational): |
Raymond Hettinger | 909e334 | 2008-01-24 23:50:26 +0000 | [diff] [blame] | 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) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 378 | |
| 379 | def __mod__(a, b): |
| 380 | """a % b""" |
Raymond Hettinger | 909e334 | 2008-01-24 23:50:26 +0000 | [diff] [blame] | 381 | div = a // b |
| 382 | return a - b * div |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 383 | |
| 384 | def __rmod__(b, a): |
| 385 | """a % b""" |
Raymond Hettinger | 909e334 | 2008-01-24 23:50:26 +0000 | [diff] [blame] | 386 | div = a // b |
| 387 | return a - b * div |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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 | """ |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 397 | if isinstance(b, Rational): |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 398 | if b.denominator == 1: |
| 399 | power = b.numerator |
| 400 | if power >= 0: |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 401 | return Fraction(a._numerator ** power, |
| 402 | a._denominator ** power) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 403 | else: |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 404 | return Fraction(a._denominator ** -power, |
| 405 | a._numerator ** -power) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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""" |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 415 | if b._denominator == 1 and b._numerator >= 0: |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 416 | # If a is an int, keep it that way if possible. |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 417 | return a ** b._numerator |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 418 | |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 419 | if isinstance(a, Rational): |
| 420 | return Fraction(a.numerator, a.denominator) ** b |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 421 | |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 422 | if b._denominator == 1: |
| 423 | return a ** b._numerator |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 424 | |
| 425 | return a ** float(b) |
| 426 | |
| 427 | def __pos__(a): |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 428 | """+a: Coerces a subclass instance to Fraction""" |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 429 | return Fraction(a._numerator, a._denominator) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 430 | |
| 431 | def __neg__(a): |
| 432 | """-a""" |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 433 | return Fraction(-a._numerator, a._denominator) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 434 | |
| 435 | def __abs__(a): |
| 436 | """abs(a)""" |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 437 | return Fraction(abs(a._numerator), a._denominator) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 438 | |
| 439 | def __trunc__(a): |
| 440 | """trunc(a)""" |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 441 | if a._numerator < 0: |
| 442 | return -(-a._numerator // a._denominator) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 443 | else: |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 444 | return a._numerator // a._denominator |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 445 | |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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 | """ |
Raymond Hettinger | 921cb5d | 2008-01-25 00:33:45 +0000 | [diff] [blame] | 453 | # XXX since this method is expensive, consider caching the result |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 454 | if self._denominator == 1: |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 455 | # Get integers right. |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 456 | return hash(self._numerator) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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. |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 463 | return hash((self._numerator, self._denominator)) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 464 | |
| 465 | def __eq__(a, b): |
| 466 | """a == b""" |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 467 | if isinstance(b, Rational): |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 468 | return (a._numerator == b.numerator and |
| 469 | a._denominator == b.denominator) |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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: |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 494 | # XXX: If b <: Real but not <: Rational, this is likely |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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 |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 502 | if isinstance(diff, Rational): |
Jeffrey Yasskin | d7b0033 | 2008-01-15 07:46:24 +0000 | [diff] [blame] | 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""" |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 524 | return a._numerator != 0 |
Raymond Hettinger | a621674 | 2008-01-25 00:21:54 +0000 | [diff] [blame] | 525 | |
| 526 | # support for pickling, copy, and deepcopy |
| 527 | |
| 528 | def __reduce__(self): |
| 529 | return (self.__class__, (str(self),)) |
| 530 | |
| 531 | def __copy__(self): |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 532 | if type(self) == Fraction: |
Raymond Hettinger | a621674 | 2008-01-25 00:21:54 +0000 | [diff] [blame] | 533 | return self # I'm immutable; therefore I am my own clone |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 534 | return self.__class__(self._numerator, self._denominator) |
Raymond Hettinger | a621674 | 2008-01-25 00:21:54 +0000 | [diff] [blame] | 535 | |
| 536 | def __deepcopy__(self, memo): |
Mark Dickinson | d058cd2 | 2008-02-10 21:29:51 +0000 | [diff] [blame] | 537 | if type(self) == Fraction: |
Raymond Hettinger | a621674 | 2008-01-25 00:21:54 +0000 | [diff] [blame] | 538 | return self # My components are also immutable |
Jeffrey Yasskin | 339f5e3 | 2008-02-14 07:49:25 +0000 | [diff] [blame] | 539 | return self.__class__(self._numerator, self._denominator) |