Author rhettinger
Recipients Sergey.Kirpichev, mark.dickinson, rhettinger
Date 2021-03-06.20:00:34
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1615060834.29.0.273600518162.issue43420@roundup.psfhosted.org>
In-reply-to
Content
Note that Fraction arithmetic has a huge administrative overhead. The cost of the underlying multiplications and divisions won't dominate the total time until the numerators and denominators are very large.

For the proposed optimization, this implies that cost for the extra Python steps to implement the optimization will be negligible.  The benefits of the optimization are similarly attenuated.

-- Update to experimentation code: add guards for the relatively prime case. --

class Henrici(Fraction):
    'Reformulate _mul to reduce the size of intermediate products'
    def _mul(a, b):
        a_n, a_d = a.numerator, a.denominator
        b_n, b_d = b.numerator, b.denominator
        d1 = math.gcd(a_n, b_d)
        if d1 > 1:
            a_n //= d1
            b_d //= d1
        d2 = math.gcd(b_n, a_d)
        if d2 > 1:
            b_n //= d2
            a_d //= d2
        result = Fraction(a_n * b_n, a_d * b_d, _normalize=False)
        assert math.gcd(a_n * b_n, a_d * b_d) == 1 and a_d * b_d >= 0
        return result
History
Date User Action Args
2021-03-06 20:00:34rhettingersetrecipients: + rhettinger, mark.dickinson, Sergey.Kirpichev
2021-03-06 20:00:34rhettingersetmessageid: <1615060834.29.0.273600518162.issue43420@roundup.psfhosted.org>
2021-03-06 20:00:34rhettingerlinkissue43420 messages
2021-03-06 20:00:34rhettingercreate