[issue37863] Speed up hash(fractions.Fraction)

[Mark Dickinson]

Mark Dickinson <dickinsm at gmail.com> added the comment:

> That's a major difference between exponents of bit lengths 61 ((P-2).bit_length()) and 1 ((1).bit_length()).

Right, but that's stacked up against the cost of the extended Euclidean algorithm for computing the inverse. The extended gcd for computing the inverse of 1425089352415399815 (for example) modulo 2**61 - 1 takes 69 steps, each one of which involves a PyLong quotient-and-remainder division, a PyLong multiplication and a subtraction. So that's at least the same order of magnitude when it comes to number of operations.

I'd bet that a dedicated pure C square-and-multiply algorithm (with an addition chain specifically chosen for the target modulus, and with the multiplication and reduction specialised for the particular form of the modulus) would still be the fastest way to go here. I believe optimal addition chains for 2**31-3 are known, and it shouldn't be too hard to find something close-to-optimal (as opposed to proved optimal) for 2**61-3.

----------

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