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
12 __all__
= ['Fraction', 'gcd']
14 Rational
= numbers
.Rational
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).
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
36 \.(?P<decimal>\d*) # decimal point and fractional part
38 \s*\Z # and optional whitespace to finish
42 class Fraction(Rational
):
43 """This class implements rational numbers.
45 Fraction(8, 6) will produce a rational number equivalent to
46 4/3. Both arguments must be Integral. The numerator defaults to 0
47 and the denominator defaults to 1 so that Fraction(3) == 3 and
50 Fractions can also be constructed from strings of the form
51 '[-+]?[0-9]+((/|.)[0-9]+)?', optionally surrounded by spaces.
55 __slots__
= ('_numerator', '_denominator')
57 # We're immutable, so use __new__ not __init__
58 def __new__(cls
, numerator
=0, denominator
=1):
59 """Constructs a Fraction.
61 Takes a string like '3/2' or '1.5', another Fraction, or a
62 numerator/denominator pair.
65 self
= super(Fraction
, cls
).__new
__(cls
)
67 if type(numerator
) not in (int, long) and denominator
== 1:
68 if isinstance(numerator
, basestring
):
69 # Handle construction from strings.
71 m
= _RATIONAL_FORMAT
.match(input)
73 raise ValueError('Invalid literal for Fraction: ' + input)
74 numerator
= m
.group('num')
75 decimal
= m
.group('decimal')
77 # The literal is a decimal number.
78 numerator
= int(numerator
+ decimal
)
79 denominator
= 10**len(decimal
)
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)
86 if m
.group('sign') == '-':
87 numerator
= -numerator
89 elif isinstance(numerator
, Rational
):
90 # Handle copies from other rationals. Integrals get
91 # caught here too, but it doesn't matter because
92 # denominator is already 1.
93 other_rational
= numerator
94 numerator
= other_rational
.numerator
95 denominator
= other_rational
.denominator
98 raise ZeroDivisionError('Fraction(%s, 0)' % numerator
)
100 numerator
= numerator
.__index
__()
101 denominator
= denominator
.__index
__()
102 g
= gcd(numerator
, denominator
)
103 self
._numerator
= numerator
// g
104 self
._denominator
= denominator
// g
108 def from_float(cls
, f
):
109 """Converts a finite float to a rational number, exactly.
111 Beware that Fraction.from_float(0.3) != Fraction(3, 10).
114 if not isinstance(f
, float):
115 raise TypeError("%s.from_float() only takes floats, not %r (%s)" %
116 (cls
.__name
__, f
, type(f
).__name
__))
117 if math
.isnan(f
) or math
.isinf(f
):
118 raise TypeError("Cannot convert %r to %s." % (f
, cls
.__name
__))
119 return cls(*f
.as_integer_ratio())
122 def from_decimal(cls
, dec
):
123 """Converts a finite Decimal instance to a rational number, exactly."""
124 from decimal
import Decimal
125 if not isinstance(dec
, Decimal
):
127 "%s.from_decimal() only takes Decimals, not %r (%s)" %
128 (cls
.__name
__, dec
, type(dec
).__name
__))
129 if not dec
.is_finite():
130 # Catches infinities and nans.
131 raise TypeError("Cannot convert %s to %s." % (dec
, cls
.__name
__))
132 sign
, digits
, exp
= dec
.as_tuple()
133 digits
= int(''.join(map(str, digits
)))
137 return cls(digits
* 10 ** exp
)
139 return cls(digits
, 10 ** -exp
)
141 def limit_denominator(self
, max_denominator
=1000000):
142 """Closest Fraction to self with denominator at most max_denominator.
144 >>> Fraction('3.141592653589793').limit_denominator(10)
146 >>> Fraction('3.141592653589793').limit_denominator(100)
148 >>> Fraction(1234, 5678).limit_denominator(10000)
152 # Algorithm notes: For any real number x, define a *best upper
153 # approximation* to x to be a rational number p/q such that:
156 # (2) if p/q > r/s >= x then s > q, for any rational r/s.
158 # Define *best lower approximation* similarly. Then it can be
159 # proved that a rational number is a best upper or lower
160 # approximation to x if, and only if, it is a convergent or
161 # semiconvergent of the (unique shortest) continued fraction
164 # To find a best rational approximation with denominator <= M,
165 # we find the best upper and lower approximations with
166 # denominator <= M and take whichever of these is closer to x.
167 # In the event of a tie, the bound with smaller denominator is
168 # chosen. If both denominators are equal (which can happen
169 # only when max_denominator == 1 and self is midway between
170 # two integers) the lower bound---i.e., the floor of self, is
173 if max_denominator
< 1:
174 raise ValueError("max_denominator should be at least 1")
175 if self
._denominator
<= max_denominator
:
176 return Fraction(self
)
178 p0
, q0
, p1
, q1
= 0, 1, 1, 0
179 n
, d
= self
._numerator
, self
._denominator
183 if q2
> max_denominator
:
185 p0
, q0
, p1
, q1
= p1
, q1
, p0
+a
*p1
, q2
188 k
= (max_denominator
-q0
)//q1
189 bound1
= Fraction(p0
+k
*p1
, q0
+k
*q1
)
190 bound2
= Fraction(p1
, q1
)
191 if abs(bound2
- self
) <= abs(bound1
-self
):
202 return a
._denominator
206 return ('Fraction(%r, %r)' % (self
._numerator
, self
._denominator
))
210 if self
._denominator
== 1:
211 return str(self
._numerator
)
213 return '%s/%s' % (self
._numerator
, self
._denominator
)
215 def _operator_fallbacks(monomorphic_operator
, fallback_operator
):
216 """Generates forward and reverse operators given a purely-rational
217 operator and a function from the operator module.
220 __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op)
222 In general, we want to implement the arithmetic operations so
223 that mixed-mode operations either call an implementation whose
224 author knew about the types of both arguments, or convert both
225 to the nearest built in type and do the operation there. In
226 Fraction, that means that we define __add__ and __radd__ as:
228 def __add__(self, other):
229 # Both types have numerators/denominator attributes,
230 # so do the operation directly
231 if isinstance(other, (int, long, Fraction)):
232 return Fraction(self.numerator * other.denominator +
233 other.numerator * self.denominator,
234 self.denominator * other.denominator)
235 # float and complex don't have those operations, but we
236 # know about those types, so special case them.
237 elif isinstance(other, float):
238 return float(self) + other
239 elif isinstance(other, complex):
240 return complex(self) + other
241 # Let the other type take over.
242 return NotImplemented
244 def __radd__(self, other):
245 # radd handles more types than add because there's
246 # nothing left to fall back to.
247 if isinstance(other, Rational):
248 return Fraction(self.numerator * other.denominator +
249 other.numerator * self.denominator,
250 self.denominator * other.denominator)
251 elif isinstance(other, Real):
252 return float(other) + float(self)
253 elif isinstance(other, Complex):
254 return complex(other) + complex(self)
255 return NotImplemented
258 There are 5 different cases for a mixed-type addition on
259 Fraction. I'll refer to all of the above code that doesn't
260 refer to Fraction, float, or complex as "boilerplate". 'r'
261 will be an instance of Fraction, which is a subtype of
262 Rational (r : Fraction <: Rational), and b : B <:
263 Complex. The first three involve 'r + b':
265 1. If B <: Fraction, int, float, or complex, we handle
266 that specially, and all is well.
267 2. If Fraction falls back to the boilerplate code, and it
268 were to return a value from __add__, we'd miss the
269 possibility that B defines a more intelligent __radd__,
270 so the boilerplate should return NotImplemented from
271 __add__. In particular, we don't handle Rational
272 here, even though we could get an exact answer, in case
273 the other type wants to do something special.
274 3. If B <: Fraction, Python tries B.__radd__ before
275 Fraction.__add__. This is ok, because it was
276 implemented with knowledge of Fraction, so it can
277 handle those instances before delegating to Real or
280 The next two situations describe 'b + r'. We assume that b
281 didn't know about Fraction in its implementation, and that it
282 uses similar boilerplate code:
284 4. If B <: Rational, then __radd_ converts both to the
285 builtin rational type (hey look, that's us) and
287 5. Otherwise, __radd__ tries to find the nearest common
288 base ABC, and fall back to its builtin type. Since this
289 class doesn't subclass a concrete type, there's no
290 implementation to fall back to, so we need to try as
291 hard as possible to return an actual value, or the user
292 will get a TypeError.
296 if isinstance(b
, (int, long, Fraction
)):
297 return monomorphic_operator(a
, b
)
298 elif isinstance(b
, float):
299 return fallback_operator(float(a
), b
)
300 elif isinstance(b
, complex):
301 return fallback_operator(complex(a
), b
)
303 return NotImplemented
304 forward
.__name
__ = '__' + fallback_operator
.__name
__ + '__'
305 forward
.__doc
__ = monomorphic_operator
.__doc
__
308 if isinstance(a
, Rational
):
310 return monomorphic_operator(a
, b
)
311 elif isinstance(a
, numbers
.Real
):
312 return fallback_operator(float(a
), float(b
))
313 elif isinstance(a
, numbers
.Complex
):
314 return fallback_operator(complex(a
), complex(b
))
316 return NotImplemented
317 reverse
.__name
__ = '__r' + fallback_operator
.__name
__ + '__'
318 reverse
.__doc
__ = monomorphic_operator
.__doc
__
320 return forward
, reverse
324 return Fraction(a
.numerator
* b
.denominator
+
325 b
.numerator
* a
.denominator
,
326 a
.denominator
* b
.denominator
)
328 __add__
, __radd__
= _operator_fallbacks(_add
, operator
.add
)
332 return Fraction(a
.numerator
* b
.denominator
-
333 b
.numerator
* a
.denominator
,
334 a
.denominator
* b
.denominator
)
336 __sub__
, __rsub__
= _operator_fallbacks(_sub
, operator
.sub
)
340 return Fraction(a
.numerator
* b
.numerator
, a
.denominator
* b
.denominator
)
342 __mul__
, __rmul__
= _operator_fallbacks(_mul
, operator
.mul
)
346 return Fraction(a
.numerator
* b
.denominator
,
347 a
.denominator
* b
.numerator
)
349 __truediv__
, __rtruediv__
= _operator_fallbacks(_div
, operator
.truediv
)
350 __div__
, __rdiv__
= _operator_fallbacks(_div
, operator
.div
)
352 def __floordiv__(a
, b
):
354 # Will be math.floor(a / b) in 3.0.
356 if isinstance(div
, Rational
):
357 # trunc(math.floor(div)) doesn't work if the rational is
358 # more precise than a float because the intermediate
359 # rounding may cross an integer boundary.
360 return div
.numerator
// div
.denominator
362 return math
.floor(div
)
364 def __rfloordiv__(b
, a
):
366 # Will be math.floor(a / b) in 3.0.
368 if isinstance(div
, Rational
):
369 # trunc(math.floor(div)) doesn't work if the rational is
370 # more precise than a float because the intermediate
371 # rounding may cross an integer boundary.
372 return div
.numerator
// div
.denominator
374 return math
.floor(div
)
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.
394 if isinstance(b
, Rational
):
395 if b
.denominator
== 1:
398 return Fraction(a
._numerator
** power
,
399 a
._denominator
** power
)
401 return Fraction(a
._denominator
** -power
,
402 a
._numerator
** -power
)
404 # A fractional power will generally produce an
406 return float(a
) ** float(b
)
412 if b
._denominator
== 1 and b
._numerator
>= 0:
413 # If a is an int, keep it that way if possible.
414 return a
** b
._numerator
416 if isinstance(a
, Rational
):
417 return Fraction(a
.numerator
, a
.denominator
) ** b
419 if b
._denominator
== 1:
420 return a
** b
._numerator
425 """+a: Coerces a subclass instance to Fraction"""
426 return Fraction(a
._numerator
, a
._denominator
)
430 return Fraction(-a
._numerator
, a
._denominator
)
434 return Fraction(abs(a
._numerator
), a
._denominator
)
439 return -(-a
._numerator
// a
._denominator
)
441 return a
._numerator
// a
._denominator
446 Tricky because values that are exactly representable as a
447 float must have the same hash as that float.
450 # XXX since this method is expensive, consider caching the result
451 if self
._denominator
== 1:
452 # Get integers right.
453 return hash(self
._numerator
)
454 # Expensive check, but definitely correct.
455 if self
== float(self
):
456 return hash(float(self
))
458 # Use tuple's hash to avoid a high collision rate on
460 return hash((self
._numerator
, self
._denominator
))
464 if isinstance(b
, Rational
):
465 return (a
._numerator
== b
.numerator
and
466 a
._denominator
== b
.denominator
)
467 if isinstance(b
, numbers
.Complex
) and b
.imag
== 0:
469 if isinstance(b
, float):
470 return a
== a
.from_float(b
)
472 # XXX: If b.__eq__ is implemented like this method, it may
473 # give the wrong answer after float(a) changes a's
474 # value. Better ways of doing this are welcome.
477 def _subtractAndCompareToZero(a
, b
, op
):
478 """Helper function for comparison operators.
480 Subtracts b from a, exactly if possible, and compares the
481 result with 0 using op, in such a way that the comparison
482 won't recurse. If the difference raises a TypeError, returns
483 NotImplemented instead.
486 if isinstance(b
, numbers
.Complex
) and b
.imag
== 0:
488 if isinstance(b
, float):
491 # XXX: If b <: Real but not <: Rational, this is likely
492 # to fall back to a float. If the actual values differ by
493 # less than MIN_FLOAT, this could falsely call them equal,
494 # which would make <= inconsistent with ==. Better ways of
495 # doing this are welcome.
498 return NotImplemented
499 if isinstance(diff
, Rational
):
500 return op(diff
.numerator
, 0)
505 return a
._subtractAndCompareToZero
(b
, operator
.lt
)
509 return a
._subtractAndCompareToZero
(b
, operator
.gt
)
513 return a
._subtractAndCompareToZero
(b
, operator
.le
)
517 return a
._subtractAndCompareToZero
(b
, operator
.ge
)
521 return a
._numerator
!= 0
523 # support for pickling, copy, and deepcopy
525 def __reduce__(self
):
526 return (self
.__class
__, (str(self
),))
529 if type(self
) == Fraction
:
530 return self
# I'm immutable; therefore I am my own clone
531 return self
.__class
__(self
._numerator
, self
._denominator
)
533 def __deepcopy__(self
, memo
):
534 if type(self
) == Fraction
:
535 return self
# My components are also immutable
536 return self
.__class
__(self
._numerator
, self
._denominator
)