From 420f0df862cf2290ad6a5e25286925ad197c9ef5 Mon Sep 17 00:00:00 2001 From: Mark Dickinson Date: Tue, 21 Jun 2022 20:36:35 +0100 Subject: 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. --- Lib/fractions.py | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) diff --git a/Lib/fractions.py b/Lib/fractions.py index f9ac882..738a0d4 100644 --- a/Lib/fractions.py +++ b/Lib/fractions.py @@ -245,14 +245,16 @@ class Fraction(numbers.Rational): 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): -- cgit v0.12