blob: 8be52d2db88ca6afda2f18786e6a41b5de62f279 [file] [log] [blame]
Guido van Rossum7736b5b2008-01-15 21:44:53 +00001# Originally contributed by Sjoerd Mullender.
2# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>.
3
Christian Heimes3feef612008-02-11 06:19:17 +00004"""Fraction, infinite-precision, real numbers."""
Guido van Rossum7736b5b2008-01-15 21:44:53 +00005
Mark Dickinson98127c32010-04-03 11:18:52 +00006from decimal import Decimal
Guido van Rossum7736b5b2008-01-15 21:44:53 +00007import math
8import numbers
9import operator
Christian Heimes587c2bf2008-01-19 16:21:02 +000010import re
Mark Dickinsondc787d22010-05-23 13:33:13 +000011import sys
Guido van Rossum7736b5b2008-01-15 21:44:53 +000012
Raymond Hettingere580f5c2008-05-08 16:03:04 +000013__all__ = ['Fraction', 'gcd']
Guido van Rossum7736b5b2008-01-15 21:44:53 +000014
Guido van Rossum7736b5b2008-01-15 21:44:53 +000015
16
Christian Heimesaf98da12008-01-27 15:18:18 +000017def gcd(a, b):
18 """Calculate the Greatest Common Divisor of a and b.
Guido van Rossum7736b5b2008-01-15 21:44:53 +000019
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
Mark Dickinsondc787d22010-05-23 13:33:13 +000027# Constants related to the hash implementation; hash(x) is based
28# on the reduction of x modulo the prime _PyHASH_MODULUS.
29_PyHASH_MODULUS = sys.hash_info.modulus
30# Value to be used for rationals that reduce to infinity modulo
31# _PyHASH_MODULUS.
32_PyHASH_INF = sys.hash_info.inf
Guido van Rossum7736b5b2008-01-15 21:44:53 +000033
Christian Heimes292d3512008-02-03 16:51:08 +000034_RATIONAL_FORMAT = re.compile(r"""
35 \A\s* # optional whitespace at the start, then
36 (?P<sign>[-+]?) # an optional sign, then
37 (?=\d|\.\d) # lookahead for digit or .digit
38 (?P<num>\d*) # numerator (possibly empty)
Mark Dickinsoncf63f2f2009-04-22 17:50:21 +000039 (?: # followed by
40 (?:/(?P<denom>\d+))? # an optional denominator
Christian Heimes292d3512008-02-03 16:51:08 +000041 | # or
Mark Dickinsoncf63f2f2009-04-22 17:50:21 +000042 (?:\.(?P<decimal>\d*))? # an optional fractional part
43 (?:E(?P<exp>[-+]?\d+))? # and optional exponent
44 )
Christian Heimes292d3512008-02-03 16:51:08 +000045 \s*\Z # and optional whitespace to finish
Mark Dickinsoncf63f2f2009-04-22 17:50:21 +000046""", re.VERBOSE | re.IGNORECASE)
Christian Heimes587c2bf2008-01-19 16:21:02 +000047
48
Christian Heimes3feef612008-02-11 06:19:17 +000049class Fraction(numbers.Rational):
Guido van Rossum7736b5b2008-01-15 21:44:53 +000050 """This class implements rational numbers.
51
Mark Dickinson98127c32010-04-03 11:18:52 +000052 In the two-argument form of the constructor, Fraction(8, 6) will
53 produce a rational number equivalent to 4/3. Both arguments must
54 be Rational. The numerator defaults to 0 and the denominator
55 defaults to 1 so that Fraction(3) == 3 and Fraction() == 0.
Guido van Rossum7736b5b2008-01-15 21:44:53 +000056
Mark Dickinson98127c32010-04-03 11:18:52 +000057 Fractions can also be constructed from:
58
59 - numeric strings similar to those accepted by the
60 float constructor (for example, '-2.3' or '1e10')
61
62 - strings of the form '123/456'
63
64 - float and Decimal instances
65
66 - other Rational instances (including integers)
Christian Heimes587c2bf2008-01-19 16:21:02 +000067
Guido van Rossum7736b5b2008-01-15 21:44:53 +000068 """
69
Christian Heimes400adb02008-02-01 08:12:03 +000070 __slots__ = ('_numerator', '_denominator')
Guido van Rossum7736b5b2008-01-15 21:44:53 +000071
Christian Heimes587c2bf2008-01-19 16:21:02 +000072 # We're immutable, so use __new__ not __init__
Mark Dickinsond4d95f82009-04-24 14:06:19 +000073 def __new__(cls, numerator=0, denominator=None):
Christian Heimes587c2bf2008-01-19 16:21:02 +000074 """Constructs a Rational.
75
Mark Dickinson98127c32010-04-03 11:18:52 +000076 Takes a string like '3/2' or '1.5', another Rational instance, a
77 numerator/denominator pair, or a float.
78
79 Examples
80 --------
81
82 >>> Fraction(10, -8)
83 Fraction(-5, 4)
84 >>> Fraction(Fraction(1, 7), 5)
85 Fraction(1, 35)
86 >>> Fraction(Fraction(1, 7), Fraction(2, 3))
87 Fraction(3, 14)
88 >>> Fraction('314')
89 Fraction(314, 1)
90 >>> Fraction('-35/4')
91 Fraction(-35, 4)
92 >>> Fraction('3.1415') # conversion from numeric string
93 Fraction(6283, 2000)
94 >>> Fraction('-47e-2') # string may include a decimal exponent
95 Fraction(-47, 100)
96 >>> Fraction(1.47) # direct construction from float (exact conversion)
97 Fraction(6620291452234629, 4503599627370496)
98 >>> Fraction(2.25)
99 Fraction(9, 4)
100 >>> Fraction(Decimal('1.47'))
101 Fraction(147, 100)
Christian Heimes587c2bf2008-01-19 16:21:02 +0000102
103 """
Christian Heimes3feef612008-02-11 06:19:17 +0000104 self = super(Fraction, cls).__new__(cls)
Christian Heimes587c2bf2008-01-19 16:21:02 +0000105
Mark Dickinsond4d95f82009-04-24 14:06:19 +0000106 if denominator is None:
107 if isinstance(numerator, numbers.Rational):
108 self._numerator = numerator.numerator
109 self._denominator = numerator.denominator
110 return self
111
Mark Dickinson98127c32010-04-03 11:18:52 +0000112 elif isinstance(numerator, float):
113 # Exact conversion from float
114 value = Fraction.from_float(numerator)
115 self._numerator = value._numerator
116 self._denominator = value._denominator
117 return self
118
119 elif isinstance(numerator, Decimal):
120 value = Fraction.from_decimal(numerator)
121 self._numerator = value._numerator
122 self._denominator = value._denominator
123 return self
124
Mark Dickinsond4d95f82009-04-24 14:06:19 +0000125 elif isinstance(numerator, str):
Christian Heimes587c2bf2008-01-19 16:21:02 +0000126 # Handle construction from strings.
Mark Dickinsoncf63f2f2009-04-22 17:50:21 +0000127 m = _RATIONAL_FORMAT.match(numerator)
Christian Heimes587c2bf2008-01-19 16:21:02 +0000128 if m is None:
Mark Dickinsoncf63f2f2009-04-22 17:50:21 +0000129 raise ValueError('Invalid literal for Fraction: %r' %
130 numerator)
131 numerator = int(m.group('num') or '0')
132 denom = m.group('denom')
133 if denom:
134 denominator = int(denom)
Christian Heimesaf98da12008-01-27 15:18:18 +0000135 else:
Mark Dickinsoncf63f2f2009-04-22 17:50:21 +0000136 denominator = 1
137 decimal = m.group('decimal')
138 if decimal:
139 scale = 10**len(decimal)
140 numerator = numerator * scale + int(decimal)
141 denominator *= scale
142 exp = m.group('exp')
143 if exp:
144 exp = int(exp)
145 if exp >= 0:
146 numerator *= 10**exp
147 else:
148 denominator *= 10**-exp
Christian Heimes587c2bf2008-01-19 16:21:02 +0000149 if m.group('sign') == '-':
150 numerator = -numerator
151
Mark Dickinsond4d95f82009-04-24 14:06:19 +0000152 else:
153 raise TypeError("argument should be a string "
154 "or a Rational instance")
155
156 elif (isinstance(numerator, numbers.Rational) and
157 isinstance(denominator, numbers.Rational)):
158 numerator, denominator = (
159 numerator.numerator * denominator.denominator,
160 denominator.numerator * numerator.denominator
161 )
162 else:
163 raise TypeError("both arguments should be "
164 "Rational instances")
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000165
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000166 if denominator == 0:
Christian Heimes3feef612008-02-11 06:19:17 +0000167 raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
Christian Heimesaf98da12008-01-27 15:18:18 +0000168 g = gcd(numerator, denominator)
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000169 self._numerator = numerator // g
170 self._denominator = denominator // g
Christian Heimes587c2bf2008-01-19 16:21:02 +0000171 return self
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000172
173 @classmethod
174 def from_float(cls, f):
Christian Heimes587c2bf2008-01-19 16:21:02 +0000175 """Converts a finite float to a rational number, exactly.
176
Christian Heimes3feef612008-02-11 06:19:17 +0000177 Beware that Fraction.from_float(0.3) != Fraction(3, 10).
Christian Heimes587c2bf2008-01-19 16:21:02 +0000178
179 """
Georg Brandl2ee470f2008-07-16 12:55:28 +0000180 if isinstance(f, numbers.Integral):
Georg Brandl3a9b0622009-01-03 22:07:57 +0000181 return cls(f)
Georg Brandl2ee470f2008-07-16 12:55:28 +0000182 elif not isinstance(f, float):
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000183 raise TypeError("%s.from_float() only takes floats, not %r (%s)" %
184 (cls.__name__, f, type(f).__name__))
185 if math.isnan(f) or math.isinf(f):
186 raise TypeError("Cannot convert %r to %s." % (f, cls.__name__))
Christian Heimes26855632008-01-27 23:50:43 +0000187 return cls(*f.as_integer_ratio())
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000188
Christian Heimes587c2bf2008-01-19 16:21:02 +0000189 @classmethod
190 def from_decimal(cls, dec):
191 """Converts a finite Decimal instance to a rational number, exactly."""
192 from decimal import Decimal
Georg Brandl2ee470f2008-07-16 12:55:28 +0000193 if isinstance(dec, numbers.Integral):
194 dec = Decimal(int(dec))
195 elif not isinstance(dec, Decimal):
Christian Heimes587c2bf2008-01-19 16:21:02 +0000196 raise TypeError(
197 "%s.from_decimal() only takes Decimals, not %r (%s)" %
198 (cls.__name__, dec, type(dec).__name__))
199 if not dec.is_finite():
200 # Catches infinities and nans.
201 raise TypeError("Cannot convert %s to %s." % (dec, cls.__name__))
202 sign, digits, exp = dec.as_tuple()
203 digits = int(''.join(map(str, digits)))
204 if sign:
205 digits = -digits
206 if exp >= 0:
207 return cls(digits * 10 ** exp)
208 else:
209 return cls(digits, 10 ** -exp)
210
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000211 def limit_denominator(self, max_denominator=1000000):
212 """Closest Fraction to self with denominator at most max_denominator.
Christian Heimesbbffeb62008-01-24 09:42:52 +0000213
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000214 >>> Fraction('3.141592653589793').limit_denominator(10)
215 Fraction(22, 7)
216 >>> Fraction('3.141592653589793').limit_denominator(100)
217 Fraction(311, 99)
Mark Dickinsondfb15622009-11-23 16:27:17 +0000218 >>> Fraction(4321, 8765).limit_denominator(10000)
219 Fraction(4321, 8765)
Christian Heimesbbffeb62008-01-24 09:42:52 +0000220
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000221 """
222 # Algorithm notes: For any real number x, define a *best upper
223 # approximation* to x to be a rational number p/q such that:
224 #
225 # (1) p/q >= x, and
226 # (2) if p/q > r/s >= x then s > q, for any rational r/s.
227 #
228 # Define *best lower approximation* similarly. Then it can be
229 # proved that a rational number is a best upper or lower
230 # approximation to x if, and only if, it is a convergent or
231 # semiconvergent of the (unique shortest) continued fraction
232 # associated to x.
233 #
234 # To find a best rational approximation with denominator <= M,
235 # we find the best upper and lower approximations with
236 # denominator <= M and take whichever of these is closer to x.
237 # In the event of a tie, the bound with smaller denominator is
238 # chosen. If both denominators are equal (which can happen
239 # only when max_denominator == 1 and self is midway between
240 # two integers) the lower bound---i.e., the floor of self, is
241 # taken.
242
243 if max_denominator < 1:
244 raise ValueError("max_denominator should be at least 1")
245 if self._denominator <= max_denominator:
246 return Fraction(self)
247
248 p0, q0, p1, q1 = 0, 1, 1, 0
249 n, d = self._numerator, self._denominator
250 while True:
251 a = n//d
252 q2 = q0+a*q1
253 if q2 > max_denominator:
Christian Heimesbbffeb62008-01-24 09:42:52 +0000254 break
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000255 p0, q0, p1, q1 = p1, q1, p0+a*p1, q2
256 n, d = d, n-a*d
257
258 k = (max_denominator-q0)//q1
259 bound1 = Fraction(p0+k*p1, q0+k*q1)
260 bound2 = Fraction(p1, q1)
261 if abs(bound2 - self) <= abs(bound1-self):
262 return bound2
263 else:
264 return bound1
Christian Heimesbbffeb62008-01-24 09:42:52 +0000265
Christian Heimes400adb02008-02-01 08:12:03 +0000266 @property
267 def numerator(a):
268 return a._numerator
269
270 @property
271 def denominator(a):
272 return a._denominator
273
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000274 def __repr__(self):
275 """repr(self)"""
Benjamin Peterson41181742008-07-02 20:22:54 +0000276 return ('Fraction(%s, %s)' % (self._numerator, self._denominator))
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000277
278 def __str__(self):
279 """str(self)"""
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000280 if self._denominator == 1:
281 return str(self._numerator)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000282 else:
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000283 return '%s/%s' % (self._numerator, self._denominator)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000284
285 def _operator_fallbacks(monomorphic_operator, fallback_operator):
286 """Generates forward and reverse operators given a purely-rational
287 operator and a function from the operator module.
288
289 Use this like:
290 __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op)
291
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000292 In general, we want to implement the arithmetic operations so
293 that mixed-mode operations either call an implementation whose
294 author knew about the types of both arguments, or convert both
295 to the nearest built in type and do the operation there. In
Christian Heimes3feef612008-02-11 06:19:17 +0000296 Fraction, that means that we define __add__ and __radd__ as:
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000297
298 def __add__(self, other):
Christian Heimes400adb02008-02-01 08:12:03 +0000299 # Both types have numerators/denominator attributes,
300 # so do the operation directly
Christian Heimes3feef612008-02-11 06:19:17 +0000301 if isinstance(other, (int, Fraction)):
302 return Fraction(self.numerator * other.denominator +
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000303 other.numerator * self.denominator,
304 self.denominator * other.denominator)
Christian Heimes400adb02008-02-01 08:12:03 +0000305 # float and complex don't have those operations, but we
306 # know about those types, so special case them.
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000307 elif isinstance(other, float):
308 return float(self) + other
309 elif isinstance(other, complex):
310 return complex(self) + other
Christian Heimes400adb02008-02-01 08:12:03 +0000311 # Let the other type take over.
312 return NotImplemented
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000313
314 def __radd__(self, other):
315 # radd handles more types than add because there's
316 # nothing left to fall back to.
Christian Heimes3feef612008-02-11 06:19:17 +0000317 if isinstance(other, numbers.Rational):
318 return Fraction(self.numerator * other.denominator +
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000319 other.numerator * self.denominator,
320 self.denominator * other.denominator)
321 elif isinstance(other, Real):
322 return float(other) + float(self)
323 elif isinstance(other, Complex):
324 return complex(other) + complex(self)
Christian Heimes400adb02008-02-01 08:12:03 +0000325 return NotImplemented
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000326
327
328 There are 5 different cases for a mixed-type addition on
Christian Heimes3feef612008-02-11 06:19:17 +0000329 Fraction. I'll refer to all of the above code that doesn't
330 refer to Fraction, float, or complex as "boilerplate". 'r'
331 will be an instance of Fraction, which is a subtype of
332 Rational (r : Fraction <: Rational), and b : B <:
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000333 Complex. The first three involve 'r + b':
334
Christian Heimes3feef612008-02-11 06:19:17 +0000335 1. If B <: Fraction, int, float, or complex, we handle
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000336 that specially, and all is well.
Christian Heimes3feef612008-02-11 06:19:17 +0000337 2. If Fraction falls back to the boilerplate code, and it
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000338 were to return a value from __add__, we'd miss the
339 possibility that B defines a more intelligent __radd__,
340 so the boilerplate should return NotImplemented from
Christian Heimes3feef612008-02-11 06:19:17 +0000341 __add__. In particular, we don't handle Rational
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000342 here, even though we could get an exact answer, in case
343 the other type wants to do something special.
Christian Heimes3feef612008-02-11 06:19:17 +0000344 3. If B <: Fraction, Python tries B.__radd__ before
345 Fraction.__add__. This is ok, because it was
346 implemented with knowledge of Fraction, so it can
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000347 handle those instances before delegating to Real or
348 Complex.
349
350 The next two situations describe 'b + r'. We assume that b
Christian Heimes3feef612008-02-11 06:19:17 +0000351 didn't know about Fraction in its implementation, and that it
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000352 uses similar boilerplate code:
353
Christian Heimes3feef612008-02-11 06:19:17 +0000354 4. If B <: Rational, then __radd_ converts both to the
Christian Heimes7b3ce6a2008-01-31 14:31:45 +0000355 builtin rational type (hey look, that's us) and
356 proceeds.
357 5. Otherwise, __radd__ tries to find the nearest common
358 base ABC, and fall back to its builtin type. Since this
359 class doesn't subclass a concrete type, there's no
360 implementation to fall back to, so we need to try as
361 hard as possible to return an actual value, or the user
362 will get a TypeError.
363
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000364 """
365 def forward(a, b):
Christian Heimes3feef612008-02-11 06:19:17 +0000366 if isinstance(b, (int, Fraction)):
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000367 return monomorphic_operator(a, b)
368 elif isinstance(b, float):
369 return fallback_operator(float(a), b)
370 elif isinstance(b, complex):
371 return fallback_operator(complex(a), b)
372 else:
373 return NotImplemented
374 forward.__name__ = '__' + fallback_operator.__name__ + '__'
375 forward.__doc__ = monomorphic_operator.__doc__
376
377 def reverse(b, a):
Christian Heimes3feef612008-02-11 06:19:17 +0000378 if isinstance(a, numbers.Rational):
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000379 # Includes ints.
380 return monomorphic_operator(a, b)
381 elif isinstance(a, numbers.Real):
382 return fallback_operator(float(a), float(b))
383 elif isinstance(a, numbers.Complex):
384 return fallback_operator(complex(a), complex(b))
385 else:
386 return NotImplemented
387 reverse.__name__ = '__r' + fallback_operator.__name__ + '__'
388 reverse.__doc__ = monomorphic_operator.__doc__
389
390 return forward, reverse
391
392 def _add(a, b):
393 """a + b"""
Christian Heimes3feef612008-02-11 06:19:17 +0000394 return Fraction(a.numerator * b.denominator +
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000395 b.numerator * a.denominator,
396 a.denominator * b.denominator)
397
398 __add__, __radd__ = _operator_fallbacks(_add, operator.add)
399
400 def _sub(a, b):
401 """a - b"""
Christian Heimes3feef612008-02-11 06:19:17 +0000402 return Fraction(a.numerator * b.denominator -
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000403 b.numerator * a.denominator,
404 a.denominator * b.denominator)
405
406 __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)
407
408 def _mul(a, b):
409 """a * b"""
Christian Heimes3feef612008-02-11 06:19:17 +0000410 return Fraction(a.numerator * b.numerator, a.denominator * b.denominator)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000411
412 __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul)
413
414 def _div(a, b):
415 """a / b"""
Christian Heimes3feef612008-02-11 06:19:17 +0000416 return Fraction(a.numerator * b.denominator,
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000417 a.denominator * b.numerator)
418
419 __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000420
421 def __floordiv__(a, b):
422 """a // b"""
Jeffrey Yasskin9893de12008-01-17 07:36:30 +0000423 return math.floor(a / b)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000424
425 def __rfloordiv__(b, a):
426 """a // b"""
Jeffrey Yasskin9893de12008-01-17 07:36:30 +0000427 return math.floor(a / b)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000428
Christian Heimes969fe572008-01-25 11:23:10 +0000429 def __mod__(a, b):
430 """a % b"""
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000431 div = a // b
432 return a - b * div
433
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000434 def __rmod__(b, a):
435 """a % b"""
Christian Heimes969fe572008-01-25 11:23:10 +0000436 div = a // b
437 return a - b * div
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000438
439 def __pow__(a, b):
440 """a ** b
441
442 If b is not an integer, the result will be a float or complex
443 since roots are generally irrational. If b is an integer, the
444 result will be rational.
445
446 """
Christian Heimes3feef612008-02-11 06:19:17 +0000447 if isinstance(b, numbers.Rational):
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000448 if b.denominator == 1:
449 power = b.numerator
450 if power >= 0:
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000451 return Fraction(a._numerator ** power,
452 a._denominator ** power)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000453 else:
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000454 return Fraction(a._denominator ** -power,
455 a._numerator ** -power)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000456 else:
457 # A fractional power will generally produce an
458 # irrational number.
459 return float(a) ** float(b)
460 else:
461 return float(a) ** b
462
463 def __rpow__(b, a):
464 """a ** b"""
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000465 if b._denominator == 1 and b._numerator >= 0:
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000466 # If a is an int, keep it that way if possible.
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000467 return a ** b._numerator
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000468
Christian Heimes3feef612008-02-11 06:19:17 +0000469 if isinstance(a, numbers.Rational):
470 return Fraction(a.numerator, a.denominator) ** b
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000471
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000472 if b._denominator == 1:
473 return a ** b._numerator
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000474
475 return a ** float(b)
476
477 def __pos__(a):
Christian Heimes3feef612008-02-11 06:19:17 +0000478 """+a: Coerces a subclass instance to Fraction"""
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000479 return Fraction(a._numerator, a._denominator)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000480
481 def __neg__(a):
482 """-a"""
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000483 return Fraction(-a._numerator, a._denominator)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000484
485 def __abs__(a):
486 """abs(a)"""
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000487 return Fraction(abs(a._numerator), a._denominator)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000488
489 def __trunc__(a):
490 """trunc(a)"""
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000491 if a._numerator < 0:
492 return -(-a._numerator // a._denominator)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000493 else:
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000494 return a._numerator // a._denominator
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000495
496 def __floor__(a):
497 """Will be math.floor(a) in 3.0."""
498 return a.numerator // a.denominator
499
500 def __ceil__(a):
501 """Will be math.ceil(a) in 3.0."""
502 # The negations cleverly convince floordiv to return the ceiling.
503 return -(-a.numerator // a.denominator)
504
505 def __round__(self, ndigits=None):
506 """Will be round(self, ndigits) in 3.0.
507
508 Rounds half toward even.
509 """
510 if ndigits is None:
511 floor, remainder = divmod(self.numerator, self.denominator)
512 if remainder * 2 < self.denominator:
513 return floor
514 elif remainder * 2 > self.denominator:
515 return floor + 1
516 # Deal with the half case:
517 elif floor % 2 == 0:
518 return floor
519 else:
520 return floor + 1
521 shift = 10**abs(ndigits)
522 # See _operator_fallbacks.forward to check that the results of
Christian Heimes3feef612008-02-11 06:19:17 +0000523 # these operations will always be Fraction and therefore have
Jeffrey Yasskin9893de12008-01-17 07:36:30 +0000524 # round().
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000525 if ndigits > 0:
Christian Heimes3feef612008-02-11 06:19:17 +0000526 return Fraction(round(self * shift), shift)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000527 else:
Christian Heimes3feef612008-02-11 06:19:17 +0000528 return Fraction(round(self / shift) * shift)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000529
530 def __hash__(self):
Mark Dickinsonfec66202010-11-13 10:27:38 +0000531 """hash(self)"""
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000532
Christian Heimes969fe572008-01-25 11:23:10 +0000533 # XXX since this method is expensive, consider caching the result
Mark Dickinsondc787d22010-05-23 13:33:13 +0000534
535 # In order to make sure that the hash of a Fraction agrees
536 # with the hash of a numerically equal integer, float or
537 # Decimal instance, we follow the rules for numeric hashes
538 # outlined in the documentation. (See library docs, 'Built-in
539 # Types').
540
541 # dinv is the inverse of self._denominator modulo the prime
542 # _PyHASH_MODULUS, or 0 if self._denominator is divisible by
543 # _PyHASH_MODULUS.
544 dinv = pow(self._denominator, _PyHASH_MODULUS - 2, _PyHASH_MODULUS)
545 if not dinv:
546 hash_ = _PyHASH_INF
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000547 else:
Mark Dickinsondc787d22010-05-23 13:33:13 +0000548 hash_ = abs(self._numerator) * dinv % _PyHASH_MODULUS
Mark Dickinsonfec66202010-11-13 10:27:38 +0000549 result = hash_ if self >= 0 else -hash_
550 return -2 if result == -1 else result
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000551
552 def __eq__(a, b):
553 """a == b"""
Christian Heimes3feef612008-02-11 06:19:17 +0000554 if isinstance(b, numbers.Rational):
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000555 return (a._numerator == b.numerator and
556 a._denominator == b.denominator)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000557 if isinstance(b, numbers.Complex) and b.imag == 0:
558 b = b.real
559 if isinstance(b, float):
Mark Dickinson85424c92009-07-18 14:41:42 +0000560 if math.isnan(b) or math.isinf(b):
561 # comparisons with an infinity or nan should behave in
562 # the same way for any finite a, so treat a as zero.
563 return 0.0 == b
564 else:
565 return a == a.from_float(b)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000566 else:
Mark Dickinson85424c92009-07-18 14:41:42 +0000567 # Since a doesn't know how to compare with b, let's give b
568 # a chance to compare itself with a.
569 return NotImplemented
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000570
Mark Dickinson85424c92009-07-18 14:41:42 +0000571 def _richcmp(self, other, op):
572 """Helper for comparison operators, for internal use only.
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000573
Mark Dickinson85424c92009-07-18 14:41:42 +0000574 Implement comparison between a Rational instance `self`, and
575 either another Rational instance or a float `other`. If
576 `other` is not a Rational instance or a float, return
577 NotImplemented. `op` should be one of the six standard
578 comparison operators.
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000579
580 """
Mark Dickinson85424c92009-07-18 14:41:42 +0000581 # convert other to a Rational instance where reasonable.
582 if isinstance(other, numbers.Rational):
583 return op(self._numerator * other.denominator,
584 self._denominator * other.numerator)
Mark Dickinson85424c92009-07-18 14:41:42 +0000585 if isinstance(other, float):
586 if math.isnan(other) or math.isinf(other):
587 return op(0.0, other)
588 else:
589 return op(self, self.from_float(other))
590 else:
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000591 return NotImplemented
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000592
593 def __lt__(a, b):
594 """a < b"""
Mark Dickinson85424c92009-07-18 14:41:42 +0000595 return a._richcmp(b, operator.lt)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000596
597 def __gt__(a, b):
598 """a > b"""
Mark Dickinson85424c92009-07-18 14:41:42 +0000599 return a._richcmp(b, operator.gt)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000600
601 def __le__(a, b):
602 """a <= b"""
Mark Dickinson85424c92009-07-18 14:41:42 +0000603 return a._richcmp(b, operator.le)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000604
605 def __ge__(a, b):
606 """a >= b"""
Mark Dickinson85424c92009-07-18 14:41:42 +0000607 return a._richcmp(b, operator.ge)
Guido van Rossum7736b5b2008-01-15 21:44:53 +0000608
609 def __bool__(a):
610 """a != 0"""
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000611 return a._numerator != 0
Christian Heimes969fe572008-01-25 11:23:10 +0000612
613 # support for pickling, copy, and deepcopy
614
615 def __reduce__(self):
616 return (self.__class__, (str(self),))
617
618 def __copy__(self):
Christian Heimes3feef612008-02-11 06:19:17 +0000619 if type(self) == Fraction:
Christian Heimes969fe572008-01-25 11:23:10 +0000620 return self # I'm immutable; therefore I am my own clone
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000621 return self.__class__(self._numerator, self._denominator)
Christian Heimes969fe572008-01-25 11:23:10 +0000622
623 def __deepcopy__(self, memo):
Christian Heimes3feef612008-02-11 06:19:17 +0000624 if type(self) == Fraction:
Christian Heimes969fe572008-01-25 11:23:10 +0000625 return self # My components are also immutable
Christian Heimes68f5fbe2008-02-14 08:27:37 +0000626 return self.__class__(self._numerator, self._denominator)