[issue43420] Optimize rational arithmetics

[Sergey B Kirpichev]

Sergey B Kirpichev <skirpichev at gmail.com> added the comment:

On Sun, Mar 07, 2021 at 10:34:24PM +0000, Aaron Meurer wrote:
> I'm surprised to hear that the "typical use-case" of Fraction
> is fractions converted from floats.

For statistics module - that may be true.  Unfortunately, no
(other) practical applications, using Fraction's, were proposed by
my reviewers so far.

> By the way, the "algorithm" here really isn't that
> complicated. I didn't even realize it had a name.

Rather "algorithms"; everything is there in the II-nd volume of
the Knuth, section 4.5 - Rational Arithmetic.  Probably, this
is even a better reference, since it explains gcd==1 case
for addition.  Both, however, reference the Henrici article.

> It's far less complicated than, for example, Lehmer's gcd
> algorithm (which is implemented in math.gcd).

Or Karatsuba multiplication.

BTW, low-denominators performance may be restored (at least
partially), using same approach (like KARATSUBA_CUTOFF - but
checking the maximal denominator).  I don't like this idea, but...

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue43420>
_______________________________________