[Python-checkins] Minor optimization for Fractions.limit_denominator (GH-93730)

Tue Jun 21 15:36:40 EDT 2022

https://github.com/python/cpython/commit/420f0df862cf2290ad6a5e25286925ad197c9ef5
commit: 420f0df862cf2290ad6a5e25286925ad197c9ef5
branch: main
author: Mark Dickinson <dickinsm at gmail.com>
committer: ambv <lukasz at langa.pl>
date: 2022年06月21日T21:36:35+02:00
summary:
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 the
denominator positive) by construction, so there's no need to go through
the usual normalisation in the constructor. This saves a couple of
potentially expensive gcd calls.
Suggested by Michael Scott Asato Cuthbert in GH-93477.
files:
M Lib/fractions.py

diff --git a/Lib/fractions.py b/Lib/fractions.py
index f9ac882ec002f..738a0d4c301d4 100644
--- a/Lib/fractions.py
+++ b/Lib/fractions.py
@@ -245,14 +245,16 @@ def limit_denominator(self, max_denominator=1000000):
 break
 p0, q0, p1, q1 = p1, q1, p0+a*p1, q2
 n, d = d, n-a*d
-
 k = (max_denominator-q0)//q1
- bound1 = Fraction(p0+k*p1, q0+k*q1)
- bound2 = Fraction(p1, q1)
- if abs(bound2 - self) <= abs(bound1-self):
- return bound2
+
+ # Determine which of the candidates (p0+k*p1)/(q0+k*q1) and p1/q1 is
+ # closer to self. The distance between them is 1/(q1*(q0+k*q1)), while
+ # the distance from p1/q1 to self is d/(q1*self._denominator). So we
+ # need to compare 2*(q0+k*q1) with self._denominator/d.
+ if 2*d*(q0+k*q1) <= self._denominator:
+ return Fraction(p1, q1, _normalize=False)
 else:
- return bound1
+ return Fraction(p0+k*p1, q0+k*q1, _normalize=False)
 
 @property
 def numerator(a):
