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