1
# Originally contributed by Sjoerd Mullender.
2
# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>.
4
"""Fraction, infinite-precision, real numbers."""
6
from decimal import Decimal
13
__all__ = ['Fraction', 'gcd']
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).
27
# 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
32
_PyHASH_INF = sys.hash_info.inf
34
_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)
40
(?:/(?P<denom>\d+))? # an optional denominator
42
(?:\.(?P<decimal>\d*))? # an optional fractional part
43
(?:E(?P<exp>[-+]?\d+))? # and optional exponent
45
\s*\Z # and optional whitespace to finish
46
""", re.VERBOSE | re.IGNORECASE)
49
class Fraction(numbers.Rational):
50
"""This class implements rational numbers.
52
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.
57
Fractions can also be constructed from:
59
- numeric strings similar to those accepted by the
60
float constructor (for example, '-2.3' or '1e10')
62
- strings of the form '123/456'
64
- float and Decimal instances
66
- other Rational instances (including integers)
70
__slots__ = ('_numerator', '_denominator')
72
# We're immutable, so use __new__ not __init__
73
def __new__(cls, numerator=0, denominator=None):
74
"""Constructs a Rational.
76
Takes a string like '3/2' or '1.5', another Rational instance, a
77
numerator/denominator pair, or a float.
84
>>> Fraction(Fraction(1, 7), 5)
86
>>> Fraction(Fraction(1, 7), Fraction(2, 3))
92
>>> Fraction('3.1415') # conversion from numeric string
94
>>> Fraction('-47e-2') # string may include a decimal exponent
96
>>> Fraction(1.47) # direct construction from float (exact conversion)
97
Fraction(6620291452234629, 4503599627370496)
100
>>> Fraction(Decimal('1.47'))
104
self = super(Fraction, cls).__new__(cls)
106
if denominator is None:
107
if isinstance(numerator, numbers.Rational):
108
self._numerator = numerator.numerator
109
self._denominator = numerator.denominator
112
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
119
elif isinstance(numerator, Decimal):
120
value = Fraction.from_decimal(numerator)
121
self._numerator = value._numerator
122
self._denominator = value._denominator
125
elif isinstance(numerator, str):
126
# Handle construction from strings.
127
m = _RATIONAL_FORMAT.match(numerator)
129
raise ValueError('Invalid literal for Fraction: %r' %
131
numerator = int(m.group('num') or '0')
132
denom = m.group('denom')
134
denominator = int(denom)
137
decimal = m.group('decimal')
139
scale = 10**len(decimal)
140
numerator = numerator * scale + int(decimal)
148
denominator *= 10**-exp
149
if m.group('sign') == '-':
150
numerator = -numerator
153
raise TypeError("argument should be a string "
154
"or a Rational instance")
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
163
raise TypeError("both arguments should be "
164
"Rational instances")
167
raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
168
g = gcd(numerator, denominator)
169
self._numerator = numerator // g
170
self._denominator = denominator // g
174
def from_float(cls, f):
175
"""Converts a finite float to a rational number, exactly.
177
Beware that Fraction.from_float(0.3) != Fraction(3, 10).
180
if isinstance(f, numbers.Integral):
182
elif not isinstance(f, float):
183
raise TypeError("%s.from_float() only takes floats, not %r (%s)" %
184
(cls.__name__, f, type(f).__name__))
186
raise ValueError("Cannot convert %r to %s." % (f, cls.__name__))
188
raise OverflowError("Cannot convert %r to %s." % (f, cls.__name__))
189
return cls(*f.as_integer_ratio())
192
def from_decimal(cls, dec):
193
"""Converts a finite Decimal instance to a rational number, exactly."""
194
from decimal import Decimal
195
if isinstance(dec, numbers.Integral):
196
dec = Decimal(int(dec))
197
elif not isinstance(dec, Decimal):
199
"%s.from_decimal() only takes Decimals, not %r (%s)" %
200
(cls.__name__, dec, type(dec).__name__))
201
if dec.is_infinite():
203
"Cannot convert %s to %s." % (dec, cls.__name__))
205
raise ValueError("Cannot convert %s to %s." % (dec, cls.__name__))
206
sign, digits, exp = dec.as_tuple()
207
digits = int(''.join(map(str, digits)))
211
return cls(digits * 10 ** exp)
213
return cls(digits, 10 ** -exp)
215
def limit_denominator(self, max_denominator=1000000):
216
"""Closest Fraction to self with denominator at most max_denominator.
218
>>> Fraction('3.141592653589793').limit_denominator(10)
220
>>> Fraction('3.141592653589793').limit_denominator(100)
222
>>> Fraction(4321, 8765).limit_denominator(10000)
226
# Algorithm notes: For any real number x, define a *best upper
227
# approximation* to x to be a rational number p/q such that:
230
# (2) if p/q > r/s >= x then s > q, for any rational r/s.
232
# Define *best lower approximation* similarly. Then it can be
233
# proved that a rational number is a best upper or lower
234
# approximation to x if, and only if, it is a convergent or
235
# semiconvergent of the (unique shortest) continued fraction
238
# To find a best rational approximation with denominator <= M,
239
# we find the best upper and lower approximations with
240
# denominator <= M and take whichever of these is closer to x.
241
# In the event of a tie, the bound with smaller denominator is
242
# chosen. If both denominators are equal (which can happen
243
# only when max_denominator == 1 and self is midway between
244
# two integers) the lower bound---i.e., the floor of self, is
247
if max_denominator < 1:
248
raise ValueError("max_denominator should be at least 1")
249
if self._denominator <= max_denominator:
250
return Fraction(self)
252
p0, q0, p1, q1 = 0, 1, 1, 0
253
n, d = self._numerator, self._denominator
257
if q2 > max_denominator:
259
p0, q0, p1, q1 = p1, q1, p0+a*p1, q2
262
k = (max_denominator-q0)//q1
263
bound1 = Fraction(p0+k*p1, q0+k*q1)
264
bound2 = Fraction(p1, q1)
265
if abs(bound2 - self) <= abs(bound1-self):
276
return a._denominator
280
return ('Fraction(%s, %s)' % (self._numerator, self._denominator))
284
if self._denominator == 1:
285
return str(self._numerator)
287
return '%s/%s' % (self._numerator, self._denominator)
289
def _operator_fallbacks(monomorphic_operator, fallback_operator):
290
"""Generates forward and reverse operators given a purely-rational
291
operator and a function from the operator module.
294
__op__, __rop__ = _operator_fallbacks(just_rational_op, operator.op)
296
In general, we want to implement the arithmetic operations so
297
that mixed-mode operations either call an implementation whose
298
author knew about the types of both arguments, or convert both
299
to the nearest built in type and do the operation there. In
300
Fraction, that means that we define __add__ and __radd__ as:
302
def __add__(self, other):
303
# Both types have numerators/denominator attributes,
304
# so do the operation directly
305
if isinstance(other, (int, Fraction)):
306
return Fraction(self.numerator * other.denominator +
307
other.numerator * self.denominator,
308
self.denominator * other.denominator)
309
# float and complex don't have those operations, but we
310
# know about those types, so special case them.
311
elif isinstance(other, float):
312
return float(self) + other
313
elif isinstance(other, complex):
314
return complex(self) + other
315
# Let the other type take over.
316
return NotImplemented
318
def __radd__(self, other):
319
# radd handles more types than add because there's
320
# nothing left to fall back to.
321
if isinstance(other, numbers.Rational):
322
return Fraction(self.numerator * other.denominator +
323
other.numerator * self.denominator,
324
self.denominator * other.denominator)
325
elif isinstance(other, Real):
326
return float(other) + float(self)
327
elif isinstance(other, Complex):
328
return complex(other) + complex(self)
329
return NotImplemented
332
There are 5 different cases for a mixed-type addition on
333
Fraction. I'll refer to all of the above code that doesn't
334
refer to Fraction, float, or complex as "boilerplate". 'r'
335
will be an instance of Fraction, which is a subtype of
336
Rational (r : Fraction <: Rational), and b : B <:
337
Complex. The first three involve 'r + b':
339
1. If B <: Fraction, int, float, or complex, we handle
340
that specially, and all is well.
341
2. If Fraction falls back to the boilerplate code, and it
342
were to return a value from __add__, we'd miss the
343
possibility that B defines a more intelligent __radd__,
344
so the boilerplate should return NotImplemented from
345
__add__. In particular, we don't handle Rational
346
here, even though we could get an exact answer, in case
347
the other type wants to do something special.
348
3. If B <: Fraction, Python tries B.__radd__ before
349
Fraction.__add__. This is ok, because it was
350
implemented with knowledge of Fraction, so it can
351
handle those instances before delegating to Real or
354
The next two situations describe 'b + r'. We assume that b
355
didn't know about Fraction in its implementation, and that it
356
uses similar boilerplate code:
358
4. If B <: Rational, then __radd_ converts both to the
359
builtin rational type (hey look, that's us) and
361
5. Otherwise, __radd__ tries to find the nearest common
362
base ABC, and fall back to its builtin type. Since this
363
class doesn't subclass a concrete type, there's no
364
implementation to fall back to, so we need to try as
365
hard as possible to return an actual value, or the user
366
will get a TypeError.
370
if isinstance(b, (int, Fraction)):
371
return monomorphic_operator(a, b)
372
elif isinstance(b, float):
373
return fallback_operator(float(a), b)
374
elif isinstance(b, complex):
375
return fallback_operator(complex(a), b)
377
return NotImplemented
378
forward.__name__ = '__' + fallback_operator.__name__ + '__'
379
forward.__doc__ = monomorphic_operator.__doc__
382
if isinstance(a, numbers.Rational):
384
return monomorphic_operator(a, b)
385
elif isinstance(a, numbers.Real):
386
return fallback_operator(float(a), float(b))
387
elif isinstance(a, numbers.Complex):
388
return fallback_operator(complex(a), complex(b))
390
return NotImplemented
391
reverse.__name__ = '__r' + fallback_operator.__name__ + '__'
392
reverse.__doc__ = monomorphic_operator.__doc__
394
return forward, reverse
398
return Fraction(a.numerator * b.denominator +
399
b.numerator * a.denominator,
400
a.denominator * b.denominator)
402
__add__, __radd__ = _operator_fallbacks(_add, operator.add)
406
return Fraction(a.numerator * b.denominator -
407
b.numerator * a.denominator,
408
a.denominator * b.denominator)
410
__sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)
414
return Fraction(a.numerator * b.numerator, a.denominator * b.denominator)
416
__mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul)
420
return Fraction(a.numerator * b.denominator,
421
a.denominator * b.numerator)
423
__truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv)
425
def __floordiv__(a, b):
427
return math.floor(a / b)
429
def __rfloordiv__(b, a):
431
return math.floor(a / b)
446
If b is not an integer, the result will be a float or complex
447
since roots are generally irrational. If b is an integer, the
448
result will be rational.
451
if isinstance(b, numbers.Rational):
452
if b.denominator == 1:
455
return Fraction(a._numerator ** power,
456
a._denominator ** power)
458
return Fraction(a._denominator ** -power,
459
a._numerator ** -power)
461
# A fractional power will generally produce an
463
return float(a) ** float(b)
469
if b._denominator == 1 and b._numerator >= 0:
470
# If a is an int, keep it that way if possible.
471
return a ** b._numerator
473
if isinstance(a, numbers.Rational):
474
return Fraction(a.numerator, a.denominator) ** b
476
if b._denominator == 1:
477
return a ** b._numerator
482
"""+a: Coerces a subclass instance to Fraction"""
483
return Fraction(a._numerator, a._denominator)
487
return Fraction(-a._numerator, a._denominator)
491
return Fraction(abs(a._numerator), a._denominator)
496
return -(-a._numerator // a._denominator)
498
return a._numerator // a._denominator
501
"""Will be math.floor(a) in 3.0."""
502
return a.numerator // a.denominator
505
"""Will be math.ceil(a) in 3.0."""
506
# The negations cleverly convince floordiv to return the ceiling.
507
return -(-a.numerator // a.denominator)
509
def __round__(self, ndigits=None):
510
"""Will be round(self, ndigits) in 3.0.
512
Rounds half toward even.
515
floor, remainder = divmod(self.numerator, self.denominator)
516
if remainder * 2 < self.denominator:
518
elif remainder * 2 > self.denominator:
520
# Deal with the half case:
525
shift = 10**abs(ndigits)
526
# See _operator_fallbacks.forward to check that the results of
527
# these operations will always be Fraction and therefore have
530
return Fraction(round(self * shift), shift)
532
return Fraction(round(self / shift) * shift)
537
# XXX since this method is expensive, consider caching the result
539
# In order to make sure that the hash of a Fraction agrees
540
# with the hash of a numerically equal integer, float or
541
# Decimal instance, we follow the rules for numeric hashes
542
# outlined in the documentation. (See library docs, 'Built-in
545
# dinv is the inverse of self._denominator modulo the prime
546
# _PyHASH_MODULUS, or 0 if self._denominator is divisible by
548
dinv = pow(self._denominator, _PyHASH_MODULUS - 2, _PyHASH_MODULUS)
552
hash_ = abs(self._numerator) * dinv % _PyHASH_MODULUS
553
result = hash_ if self >= 0 else -hash_
554
return -2 if result == -1 else result
558
if isinstance(b, numbers.Rational):
559
return (a._numerator == b.numerator and
560
a._denominator == b.denominator)
561
if isinstance(b, numbers.Complex) and b.imag == 0:
563
if isinstance(b, float):
564
if math.isnan(b) or math.isinf(b):
565
# comparisons with an infinity or nan should behave in
566
# the same way for any finite a, so treat a as zero.
569
return a == a.from_float(b)
571
# Since a doesn't know how to compare with b, let's give b
572
# a chance to compare itself with a.
573
return NotImplemented
575
def _richcmp(self, other, op):
576
"""Helper for comparison operators, for internal use only.
578
Implement comparison between a Rational instance `self`, and
579
either another Rational instance or a float `other`. If
580
`other` is not a Rational instance or a float, return
581
NotImplemented. `op` should be one of the six standard
582
comparison operators.
585
# convert other to a Rational instance where reasonable.
586
if isinstance(other, numbers.Rational):
587
return op(self._numerator * other.denominator,
588
self._denominator * other.numerator)
589
if isinstance(other, float):
590
if math.isnan(other) or math.isinf(other):
591
return op(0.0, other)
593
return op(self, self.from_float(other))
595
return NotImplemented
599
return a._richcmp(b, operator.lt)
603
return a._richcmp(b, operator.gt)
607
return a._richcmp(b, operator.le)
611
return a._richcmp(b, operator.ge)
615
return a._numerator != 0
617
# support for pickling, copy, and deepcopy
619
def __reduce__(self):
620
return (self.__class__, (str(self),))
623
if type(self) == Fraction:
624
return self # I'm immutable; therefore I am my own clone
625
return self.__class__(self._numerator, self._denominator)
627
def __deepcopy__(self, memo):
628
if type(self) == Fraction:
629
return self # My components are also immutable
630
return self.__class__(self._numerator, self._denominator)
added
removed
Lib/fractions.py
