Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commitfd98ab2

Browse files
committed
Update fractions to CPython 3.11.5
1 parent9031a0a commitfd98ab2

File tree

2 files changed

+296
-92
lines changed

2 files changed

+296
-92
lines changed

‎Lib/fractions.py‎

Lines 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
fromdecimalimportDecimal
77
importmath
@@ -10,31 +10,9 @@
1010
importre
1111
importsys
1212

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

1515

16-
17-
defgcd(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-
importwarnings
24-
warnings.warn('fractions.gcd() is deprecated. Use math.gcd() instead.',
25-
DeprecationWarning,2)
26-
iftype(a)isintistype(b):
27-
if (bora)<0:
28-
return-math.gcd(a,b)
29-
returnmath.gcd(a,b)
30-
return_gcd(a,b)
31-
32-
def_gcd(a,b):
33-
# Supports non-integers for backward compatibility.
34-
whileb:
35-
a,b=b,a%b
36-
returna
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
ifdecimal:
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
ifdenominator==0:
178157
raiseZeroDivisionError('Fraction(%s, 0)'%numerator)
179158
if_normalize:
180-
iftype(numerator)isintistype(denominator):
181-
# *very* normal case
182-
g=math.gcd(numerator,denominator)
183-
ifdenominator<0:
184-
g=-g
185-
else:
186-
g=_gcd(numerator,denominator)
159+
g=math.gcd(numerator,denominator)
160+
ifdenominator<0:
161+
g=-g
187162
numerator//=g
188163
denominator//=g
189164
self._numerator=numerator
@@ -406,32 +381,139 @@ def reverse(b, a):
406381

407382
returnforward,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-
returnFraction(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+
ifg==1:
458+
returnFraction(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+
ifg2==1:
463+
returnFraction(t,s*db,_normalize=False)
464+
returnFraction(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-
returnFraction(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+
ifg==1:
474+
returnFraction(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+
ifg2==1:
479+
returnFraction(t,s*db,_normalize=False)
480+
returnFraction(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-
returnFraction(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+
ifg1>1:
490+
na//=g1
491+
db//=g1
492+
g2=math.gcd(nb,da)
493+
ifg2>1:
494+
nb//=g2
495+
da//=g2
496+
returnFraction(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-
returnFraction(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+
ifg1>1:
507+
na//=g1
508+
nb//=g1
509+
g2=math.gcd(db,da)
510+
ifg2>1:
511+
da//=g2
512+
db//=g2
513+
n,d=na*db,nb*da
514+
ifd<0:
515+
n,d=-n,-d
516+
returnFraction(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
returnFraction(abs(a._numerator),a._denominator,_normalize=False)
514596

597+
def__int__(a,_index=operator.index):
598+
"""int(a)"""
599+
ifa._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
ifa._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-
ifnotdinv:
653+
try:
654+
dinv=pow(self._denominator,-1,_PyHASH_MODULUS)
655+
exceptValueError:
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_ifself>=0else-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_ifself._numerator>=0else-hash_
576676
return-2ifresult==-1elseresult
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
iftype(self)==Fraction:

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp