[issue43420] Optimize rational arithmetics

[Sergey B Kirpichev]

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

> I'd prefer to keep the code simplicity

It's not going to be complicated so much and algorithms are well known,
but I see your point.

> and the speed for small inputs here

Speed loss is not so big, 10-20%.

> Python's needs aren't the same as SymPy's needs or SAGE's needs

So, for which needs it will serve?

Sorry, I can't suggest an application, which does use builtin
Fraction's (not sure if even SAGE uses them, as a fallback).  SymPy doesn't,
for sure (but it could - it's PythonRational class uses same optimizations,
except for g == 1 branches in _add/_sub, I think).

There is one exception I've found: stdlib's statistics module uses Fraction's
in the _sum() helper, exactly in a paradigm "sum a lot of values".

> not all of the fractions.Fraction use-cases involve summing lots of values with incompatible denominators.

No need for a lots of values (i.e. 1000): denominator of the sum will grow very fast, that
why modern CAS use modular GCD algorithms, for example.

> Could you give some idea of the crossover point for a single addition?

$ ./python -m timeit -r11 -s 'from fractions import Fraction as F' -s 'a=F(10,31011021112)' -s 'b=F(86,11011021115)' 'a + b'
20000 loops, best of 11: 12.4 usec per loop
$ ./python -m timeit -r11 -s 'from patched import Fraction as F' -s 'a=F(10,31011021112)' -s 'b=F(86,11011021115)' 'a + b'
20000 loops, best of 11: 12.5 usec per loop

----------

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