Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit a12233e

Browse filesBrowse files
youknowoneyouknowone
authored
Merge pull request #5072 from dvermd/fractions_311
Update fractions to CPython 3.11.5
2 parents 80e7186 + fd98ab2 commit a12233e
Copy full SHA for a12233e

File tree

2 files changed

+296
-92
lines changed
Filter options

2 files changed

+296
-92
lines changed

‎Lib/fractions.py

Copy file name to clipboardExpand all lines: Lib/fractions.py
+166-66Lines changed: 166 additions & 66 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
# Originally contributed by Sjoerd Mullender.
22
# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>.
33

4-
"""Fraction, infinite-precision, real numbers."""
4+
"""Fraction, infinite-precision, rational numbers."""
55

66
from decimal import Decimal
77
import math
@@ -10,31 +10,9 @@
1010
import re
1111
import sys
1212

13-
__all__ = ['Fraction', 'gcd']
13+
__all__ = ['Fraction']
1414

1515

16-
17-
def gcd(a, b):
18-
"""Calculate the Greatest Common Divisor of a and b.
19-
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-
import warnings
24-
warnings.warn('fractions.gcd() is deprecated. Use math.gcd() instead.',
25-
DeprecationWarning, 2)
26-
if type(a) is int is type(b):
27-
if (b or a) < 0:
28-
return -math.gcd(a, b)
29-
return math.gcd(a, b)
30-
return _gcd(a, b)
31-
32-
def _gcd(a, b):
33-
# Supports non-integers for backward compatibility.
34-
while b:
35-
a, b = b, a%b
36-
return a
37-
3816
# Constants related to the hash implementation; hash(x) is based
3917
# on the reduction of x modulo the prime _PyHASH_MODULUS.
4018
_PyHASH_MODULUS = sys.hash_info.modulus
@@ -43,17 +21,17 @@ def _gcd(a, b):
4321
_PyHASH_INF = sys.hash_info.inf
4422

4523
_RATIONAL_FORMAT = re.compile(r"""
46-
\A\s* # optional whitespace at the start, then
47-
(?P<sign>[-+]?) # an optional sign, then
48-
(?=\d|\.\d) # lookahead for digit or .digit
49-
(?P<num>\d*) # numerator (possibly empty)
50-
(?: # followed by
51-
(?:/(?P<denom>\d+))? # an optional denominator
52-
| # or
53-
(?:\.(?P<decimal>\d*))? # an optional fractional part
54-
(?:E(?P<exp>[-+]?\d+))? # and optional exponent
24+
\A\s* # optional whitespace at the start,
25+
(?P<sign>[-+]?) # an optional sign, then
26+
(?=\d|\.\d) # lookahead for digit or .digit
27+
(?P<num>\d*|\d+(_\d+)*) # numerator (possibly empty)
28+
(?: # followed by
29+
(?:/(?P<denom>\d+(_\d+)*))? # an optional denominator
30+
| # or
31+
(?:\.(?P<decimal>d*|\d+(_\d+)*))? # an optional fractional part
32+
(?:E(?P<exp>[-+]?\d+(_\d+)*))? # and optional exponent
5533
)
56-
\s*\Z # and optional whitespace to finish
34+
\s*\Z # and optional whitespace to finish
5735
""", re.VERBOSE | re.IGNORECASE)
5836

5937

@@ -144,6 +122,7 @@ def __new__(cls, numerator=0, denominator=None, *, _normalize=True):
144122
denominator = 1
145123
decimal = m.group('decimal')
146124
if decimal:
125+
decimal = decimal.replace('_', '')
147126
scale = 10**len(decimal)
148127
numerator = numerator * scale + int(decimal)
149128
denominator *= scale
@@ -177,13 +156,9 @@ def __new__(cls, numerator=0, denominator=None, *, _normalize=True):
177156
if denominator == 0:
178157
raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
179158
if _normalize:
180-
if type(numerator) is int is type(denominator):
181-
# *very* normal case
182-
g = math.gcd(numerator, denominator)
183-
if denominator < 0:
184-
g = -g
185-
else:
186-
g = _gcd(numerator, denominator)
159+
g = math.gcd(numerator, denominator)
160+
if denominator < 0:
161+
g = -g
187162
numerator //= g
188163
denominator //= g
189164
self._numerator = numerator
@@ -406,32 +381,139 @@ def reverse(b, a):
406381

407382
return forward, reverse
408383

384+
# Rational arithmetic algorithms: Knuth, TAOCP, Volume 2, 4.5.1.
385+
#
386+
# Assume input fractions a and b are normalized.
387+
#
388+
# 1) Consider addition/subtraction.
389+
#
390+
# Let g = gcd(da, db). Then
391+
#
392+
# na nb na*db ± nb*da
393+
# a ± b == -- ± -- == ------------- ==
394+
# da db da*db
395+
#
396+
# na*(db//g) ± nb*(da//g) t
397+
# == ----------------------- == -
398+
# (da*db)//g d
399+
#
400+
# Now, if g > 1, we're working with smaller integers.
401+
#
402+
# Note, that t, (da//g) and (db//g) are pairwise coprime.
403+
#
404+
# Indeed, (da//g) and (db//g) share no common factors (they were
405+
# removed) and da is coprime with na (since input fractions are
406+
# normalized), hence (da//g) and na are coprime. By symmetry,
407+
# (db//g) and nb are coprime too. Then,
408+
#
409+
# gcd(t, da//g) == gcd(na*(db//g), da//g) == 1
410+
# gcd(t, db//g) == gcd(nb*(da//g), db//g) == 1
411+
#
412+
# Above allows us optimize reduction of the result to lowest
413+
# terms. Indeed,
414+
#
415+
# g2 = gcd(t, d) == gcd(t, (da//g)*(db//g)*g) == gcd(t, g)
416+
#
417+
# t//g2 t//g2
418+
# a ± b == ----------------------- == ----------------
419+
# (da//g)*(db//g)*(g//g2) (da//g)*(db//g2)
420+
#
421+
# is a normalized fraction. This is useful because the unnormalized
422+
# denominator d could be much larger than g.
423+
#
424+
# We should special-case g == 1 (and g2 == 1), since 60.8% of
425+
# randomly-chosen integers are coprime:
426+
# https://en.wikipedia.org/wiki/Coprime_integers#Probability_of_coprimality
427+
# Note, that g2 == 1 always for fractions, obtained from floats: here
428+
# g is a power of 2 and the unnormalized numerator t is an odd integer.
429+
#
430+
# 2) Consider multiplication
431+
#
432+
# Let g1 = gcd(na, db) and g2 = gcd(nb, da), then
433+
#
434+
# na*nb na*nb (na//g1)*(nb//g2)
435+
# a*b == ----- == ----- == -----------------
436+
# da*db db*da (db//g1)*(da//g2)
437+
#
438+
# Note, that after divisions we're multiplying smaller integers.
439+
#
440+
# Also, the resulting fraction is normalized, because each of
441+
# two factors in the numerator is coprime to each of the two factors
442+
# in the denominator.
443+
#
444+
# Indeed, pick (na//g1). It's coprime with (da//g2), because input
445+
# fractions are normalized. It's also coprime with (db//g1), because
446+
# common factors are removed by g1 == gcd(na, db).
447+
#
448+
# As for addition/subtraction, we should special-case g1 == 1
449+
# and g2 == 1 for same reason. That happens also for multiplying
450+
# rationals, obtained from floats.
451+
409452
def _add(a, b):
410453
"""a + b"""
411-
da, db = a.denominator, b.denominator
412-
return Fraction(a.numerator * db + b.numerator * da,
413-
da * db)
454+
na, da = a.numerator, a.denominator
455+
nb, db = b.numerator, b.denominator
456+
g = math.gcd(da, db)
457+
if g == 1:
458+
return Fraction(na * db + da * nb, da * db, _normalize=False)
459+
s = da // g
460+
t = na * (db // g) + nb * s
461+
g2 = math.gcd(t, g)
462+
if g2 == 1:
463+
return Fraction(t, s * db, _normalize=False)
464+
return Fraction(t // g2, s * (db // g2), _normalize=False)
414465

415466
__add__, __radd__ = _operator_fallbacks(_add, operator.add)
416467

417468
def _sub(a, b):
418469
"""a - b"""
419-
da, db = a.denominator, b.denominator
420-
return Fraction(a.numerator * db - b.numerator * da,
421-
da * db)
470+
na, da = a.numerator, a.denominator
471+
nb, db = b.numerator, b.denominator
472+
g = math.gcd(da, db)
473+
if g == 1:
474+
return Fraction(na * db - da * nb, da * db, _normalize=False)
475+
s = da // g
476+
t = na * (db // g) - nb * s
477+
g2 = math.gcd(t, g)
478+
if g2 == 1:
479+
return Fraction(t, s * db, _normalize=False)
480+
return Fraction(t // g2, s * (db // g2), _normalize=False)
422481

423482
__sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)
424483

425484
def _mul(a, b):
426485
"""a * b"""
427-
return Fraction(a.numerator * b.numerator, a.denominator * b.denominator)
486+
na, da = a.numerator, a.denominator
487+
nb, db = b.numerator, b.denominator
488+
g1 = math.gcd(na, db)
489+
if g1 > 1:
490+
na //= g1
491+
db //= g1
492+
g2 = math.gcd(nb, da)
493+
if g2 > 1:
494+
nb //= g2
495+
da //= g2
496+
return Fraction(na * nb, db * da, _normalize=False)
428497

429498
__mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul)
430499

431500
def _div(a, b):
432501
"""a / b"""
433-
return Fraction(a.numerator * b.denominator,
434-
a.denominator * b.numerator)
502+
# Same as _mul(), with inversed b.
503+
na, da = a.numerator, a.denominator
504+
nb, db = b.numerator, b.denominator
505+
g1 = math.gcd(na, nb)
506+
if g1 > 1:
507+
na //= g1
508+
nb //= g1
509+
g2 = math.gcd(db, da)
510+
if g2 > 1:
511+
da //= g2
512+
db //= g2
513+
n, d = na * db, nb * da
514+
if d < 0:
515+
n, d = -n, -d
516+
return Fraction(n, d, _normalize=False)
435517

436518
__truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv)
437519

@@ -512,8 +594,15 @@ def __abs__(a):
512594
"""abs(a)"""
513595
return Fraction(abs(a._numerator), a._denominator, _normalize=False)
514596

597+
def __int__(a, _index=operator.index):
598+
"""int(a)"""
599+
if a._numerator < 0:
600+
return _index(-(-a._numerator // a._denominator))
601+
else:
602+
return _index(a._numerator // a._denominator)
603+
515604
def __trunc__(a):
516-
"""trunc(a)"""
605+
"""math.trunc(a)"""
517606
if a._numerator < 0:
518607
return -(-a._numerator // a._denominator)
519608
else:
@@ -556,23 +645,34 @@ def __round__(self, ndigits=None):
556645
def __hash__(self):
557646
"""hash(self)"""
558647

559-
# XXX since this method is expensive, consider caching the result
560-
561-
# In order to make sure that the hash of a Fraction agrees
562-
# with the hash of a numerically equal integer, float or
563-
# Decimal instance, we follow the rules for numeric hashes
564-
# outlined in the documentation. (See library docs, 'Built-in
565-
# Types').
648+
# To make sure that the hash of a Fraction agrees with the hash
649+
# of a numerically equal integer, float or Decimal instance, we
650+
# follow the rules for numeric hashes outlined in the
651+
# documentation. (See library docs, 'Built-in Types').
566652

567-
# dinv is the inverse of self._denominator modulo the prime
568-
# _PyHASH_MODULUS, or 0 if self._denominator is divisible by
569-
# _PyHASH_MODULUS.
570-
dinv = pow(self._denominator, _PyHASH_MODULUS - 2, _PyHASH_MODULUS)
571-
if not dinv:
653+
try:
654+
dinv = pow(self._denominator, -1, _PyHASH_MODULUS)
655+
except ValueError:
656+
# ValueError means there is no modular inverse.
572657
hash_ = _PyHASH_INF
573658
else:
574-
hash_ = abs(self._numerator) * dinv % _PyHASH_MODULUS
575-
result = hash_ if self >= 0 else -hash_
659+
# The general algorithm now specifies that the absolute value of
660+
# the hash is
661+
# (|N| * dinv) % P
662+
# where N is self._numerator and P is _PyHASH_MODULUS. That's
663+
# optimized here in two ways: first, for a non-negative int i,
664+
# hash(i) == i % P, but the int hash implementation doesn't need
665+
# to divide, and is faster than doing % P explicitly. So we do
666+
# hash(|N| * dinv)
667+
# instead. Second, N is unbounded, so its product with dinv may
668+
# be arbitrarily expensive to compute. The final answer is the
669+
# same if we use the bounded |N| % P instead, which can again
670+
# be done with an int hash() call. If 0 <= i < P, hash(i) == i,
671+
# so this nested hash() call wastes a bit of time making a
672+
# redundant copy when |N| < P, but can save an arbitrarily large
673+
# amount of computation for large |N|.
674+
hash_ = hash(hash(abs(self._numerator)) * dinv)
675+
result = hash_ if self._numerator >= 0 else -hash_
576676
return -2 if result == -1 else result
577677

578678
def __eq__(a, b):
@@ -643,7 +743,7 @@ def __bool__(a):
643743
# support for pickling, copy, and deepcopy
644744

645745
def __reduce__(self):
646-
return (self.__class__, (str(self),))
746+
return (self.__class__, (self._numerator, self._denominator))
647747

648748
def __copy__(self):
649749
if type(self) == Fraction:

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.