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