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
11 __all__
= ["Rational"]
13 RationalAbc
= numbers
.Rational
17 """Calculate the Greatest Common Divisor.
19 Unless b==0, the result will have the same sign as b (so that when
20 b is divided by it, the result comes out positive).
27 def _binary_float_to_ratio(x
):
28 """x -> (top, bot), a pair of ints s.t. x = top/bot.
30 The conversion is done exactly, without rounding.
32 Some form of binary fp is assumed.
33 Pass NaNs or infinities at your own risk.
35 >>> _binary_float_to_ratio(10.0)
37 >>> _binary_float_to_ratio(0.0)
39 >>> _binary_float_to_ratio(-.25)
51 # x = signbit * f * 2**e exactly
53 # Suck up CHUNK bits at a time; 28 is enough so that we suck
54 # up all bits in 2 iterations for all known binary double-
55 # precision formats, and small enough to fit in an int.
58 # invariant: x = signbit * (top + f) * 2**e exactly
60 f
= math
.ldexp(f
, CHUNK
)
62 assert digit
>> CHUNK
== 0
63 top
= (top
<< CHUNK
) | digit
69 # Add in the sign bit.
72 # now x = top * 2**e exactly; fold in 2**e
74 return (top
* 2**e
, 1)
79 class Rational(RationalAbc
):
80 """This class implements rational numbers.
82 Rational(8, 6) will produce a rational number equivalent to
83 4/3. Both arguments must be Integral. The numerator defaults to 0
84 and the denominator defaults to 1 so that Rational(3) == 3 and
89 __slots__
= ('_numerator', '_denominator')
91 def __init__(self
, numerator
=0, denominator
=1):
92 if (not isinstance(numerator
, numbers
.Integral
) and
93 isinstance(numerator
, RationalAbc
) and
95 # Handle copies from other rationals.
96 other_rational
= numerator
97 numerator
= other_rational
.numerator
98 denominator
= other_rational
.denominator
100 if (not isinstance(numerator
, numbers
.Integral
) or
101 not isinstance(denominator
, numbers
.Integral
)):
102 raise TypeError("Rational(%(numerator)s, %(denominator)s):"
103 " Both arguments must be integral." % locals())
106 raise ZeroDivisionError('Rational(%s, 0)' % numerator
)
108 g
= _gcd(numerator
, denominator
)
109 self
._numerator
= int(numerator
// g
)
110 self
._denominator
= int(denominator
// g
)
113 def from_float(cls
, f
):
114 """Converts a float to a rational number, exactly."""
115 if not isinstance(f
, float):
116 raise TypeError("%s.from_float() only takes floats, not %r (%s)" %
117 (cls
.__name
__, f
, type(f
).__name
__))
118 if math
.isnan(f
) or math
.isinf(f
):
119 raise TypeError("Cannot convert %r to %s." % (f
, cls
.__name
__))
120 return cls(*_binary_float_to_ratio(f
))
128 return a
._denominator
132 return ('rational.Rational(%r,%r)' %
133 (self
.numerator
, self
.denominator
))
137 if self
.denominator
== 1:
138 return str(self
.numerator
)
140 return '(%s/%s)' % (self
.numerator
, self
.denominator
)
142 def _operator_fallbacks(monomorphic_operator
, fallback_operator
):
143 """Generates forward and reverse operators given a purely-rational
144 operator and a function from the operator module.
147 __op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op)
151 if isinstance(b
, RationalAbc
):
153 return monomorphic_operator(a
, b
)
154 elif isinstance(b
, float):
155 return fallback_operator(float(a
), b
)
156 elif isinstance(b
, complex):
157 return fallback_operator(complex(a
), b
)
159 return NotImplemented
160 forward
.__name
__ = '__' + fallback_operator
.__name
__ + '__'
161 forward
.__doc
__ = monomorphic_operator
.__doc
__
164 if isinstance(a
, RationalAbc
):
166 return monomorphic_operator(a
, b
)
167 elif isinstance(a
, numbers
.Real
):
168 return fallback_operator(float(a
), float(b
))
169 elif isinstance(a
, numbers
.Complex
):
170 return fallback_operator(complex(a
), complex(b
))
172 return NotImplemented
173 reverse
.__name
__ = '__r' + fallback_operator
.__name
__ + '__'
174 reverse
.__doc
__ = monomorphic_operator
.__doc
__
176 return forward
, reverse
180 return Rational(a
.numerator
* b
.denominator
+
181 b
.numerator
* a
.denominator
,
182 a
.denominator
* b
.denominator
)
184 __add__
, __radd__
= _operator_fallbacks(_add
, operator
.add
)
188 return Rational(a
.numerator
* b
.denominator
-
189 b
.numerator
* a
.denominator
,
190 a
.denominator
* b
.denominator
)
192 __sub__
, __rsub__
= _operator_fallbacks(_sub
, operator
.sub
)
196 return Rational(a
.numerator
* b
.numerator
, a
.denominator
* b
.denominator
)
198 __mul__
, __rmul__
= _operator_fallbacks(_mul
, operator
.mul
)
202 return Rational(a
.numerator
* b
.denominator
,
203 a
.denominator
* b
.numerator
)
205 __truediv__
, __rtruediv__
= _operator_fallbacks(_div
, operator
.truediv
)
206 __div__
, __rdiv__
= _operator_fallbacks(_div
, operator
.div
)
209 def _floordiv(cls
, a
, b
):
211 if isinstance(div
, RationalAbc
):
212 # trunc(math.floor(div)) doesn't work if the rational is
213 # more precise than a float because the intermediate
214 # rounding may cross an integer boundary.
215 return div
.numerator
// div
.denominator
217 return math
.floor(div
)
219 def __floordiv__(a
, b
):
221 # Will be math.floor(a / b) in 3.0.
222 return a
._floordiv
(a
, b
)
224 def __rfloordiv__(b
, a
):
226 # Will be math.floor(a / b) in 3.0.
227 return b
._floordiv
(a
, b
)
245 If b is not an integer, the result will be a float or complex
246 since roots are generally irrational. If b is an integer, the
247 result will be rational.
250 if isinstance(b
, RationalAbc
):
251 if b
.denominator
== 1:
254 return Rational(a
.numerator
** power
,
255 a
.denominator
** power
)
257 return Rational(a
.denominator
** -power
,
258 a
.numerator
** -power
)
260 # A fractional power will generally produce an
262 return float(a
) ** float(b
)
268 if b
.denominator
== 1 and b
.numerator
>= 0:
269 # If a is an int, keep it that way if possible.
270 return a
** b
.numerator
272 if isinstance(a
, RationalAbc
):
273 return Rational(a
.numerator
, a
.denominator
) ** b
275 if b
.denominator
== 1:
276 return a
** b
.numerator
281 """+a: Coerces a subclass instance to Rational"""
282 return Rational(a
.numerator
, a
.denominator
)
286 return Rational(-a
.numerator
, a
.denominator
)
290 return Rational(abs(a
.numerator
), a
.denominator
)
295 return -(-a
.numerator
// a
.denominator
)
297 return a
.numerator
// a
.denominator
300 """Will be math.floor(a) in 3.0."""
301 return a
.numerator
// a
.denominator
304 """Will be math.ceil(a) in 3.0."""
305 # The negations cleverly convince floordiv to return the ceiling.
306 return -(-a
.numerator
// a
.denominator
)
308 def __round__(self
, ndigits
=None):
309 """Will be round(self, ndigits) in 3.0.
311 Rounds half toward even.
314 floor
, remainder
= divmod(self
.numerator
, self
.denominator
)
315 if remainder
* 2 < self
.denominator
:
317 elif remainder
* 2 > self
.denominator
:
319 # Deal with the half case:
324 shift
= 10**abs(ndigits
)
325 # See _operator_fallbacks.forward to check that the results of
326 # these operations will always be Rational and therefore have
329 return Rational((self
* shift
).__round
__(), shift
)
331 return Rational((self
/ shift
).__round
__() * shift
)
336 Tricky because values that are exactly representable as a
337 float must have the same hash as that float.
340 if self
.denominator
== 1:
341 # Get integers right.
342 return hash(self
.numerator
)
343 # Expensive check, but definitely correct.
344 if self
== float(self
):
345 return hash(float(self
))
347 # Use tuple's hash to avoid a high collision rate on
349 return hash((self
.numerator
, self
.denominator
))
353 if isinstance(b
, RationalAbc
):
354 return (a
.numerator
== b
.numerator
and
355 a
.denominator
== b
.denominator
)
356 if isinstance(b
, numbers
.Complex
) and b
.imag
== 0:
358 if isinstance(b
, float):
359 return a
== a
.from_float(b
)
361 # XXX: If b.__eq__ is implemented like this method, it may
362 # give the wrong answer after float(a) changes a's
363 # value. Better ways of doing this are welcome.
366 def _subtractAndCompareToZero(a
, b
, op
):
367 """Helper function for comparison operators.
369 Subtracts b from a, exactly if possible, and compares the
370 result with 0 using op, in such a way that the comparison
371 won't recurse. If the difference raises a TypeError, returns
372 NotImplemented instead.
375 if isinstance(b
, numbers
.Complex
) and b
.imag
== 0:
377 if isinstance(b
, float):
380 # XXX: If b <: Real but not <: RationalAbc, this is likely
381 # to fall back to a float. If the actual values differ by
382 # less than MIN_FLOAT, this could falsely call them equal,
383 # which would make <= inconsistent with ==. Better ways of
384 # doing this are welcome.
387 return NotImplemented
388 if isinstance(diff
, RationalAbc
):
389 return op(diff
.numerator
, 0)
394 return a
._subtractAndCompareToZero
(b
, operator
.lt
)
398 return a
._subtractAndCompareToZero
(b
, operator
.gt
)
402 return a
._subtractAndCompareToZero
(b
, operator
.le
)
406 return a
._subtractAndCompareToZero
(b
, operator
.ge
)
410 return a
.numerator
!= 0