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

Commit420f0df

Browse files
authored
Minor optimization for Fractions.limit_denominator (GH-93730)
When we construct the upper and lower candidates in limit_denominator,the numerator and denominator are already relatively prime (and thedenominator positive) by construction, so there's no need to go throughthe usual normalisation in the constructor. This saves a couple ofpotentially expensive gcd calls.Suggested by Michael Scott Asato Cuthbert inGH-93477.
1 parent8305137 commit420f0df

File tree

1 file changed

+8
-6
lines changed

1 file changed

+8
-6
lines changed

‎Lib/fractions.py‎

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -245,14 +245,16 @@ def limit_denominator(self, max_denominator=1000000):
245245
break
246246
p0,q0,p1,q1=p1,q1,p0+a*p1,q2
247247
n,d=d,n-a*d
248-
249248
k= (max_denominator-q0)//q1
250-
bound1=Fraction(p0+k*p1,q0+k*q1)
251-
bound2=Fraction(p1,q1)
252-
ifabs(bound2-self)<=abs(bound1-self):
253-
returnbound2
249+
250+
# Determine which of the candidates (p0+k*p1)/(q0+k*q1) and p1/q1 is
251+
# closer to self. The distance between them is 1/(q1*(q0+k*q1)), while
252+
# the distance from p1/q1 to self is d/(q1*self._denominator). So we
253+
# need to compare 2*(q0+k*q1) with self._denominator/d.
254+
if2*d*(q0+k*q1)<=self._denominator:
255+
returnFraction(p1,q1,_normalize=False)
254256
else:
255-
returnbound1
257+
returnFraction(p0+k*p1,q0+k*q1,_normalize=False)
256258

257259
@property
258260
defnumerator(a):

0 commit comments

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