[issue37863] Speed up hash(fractions.Fraction)

Tim Peters added the comment: For posterity: "Modular Inverse Algorithms Without Multiplications for Cryptographic Applications" Laszlo Hars https://link.springer.com/article/10.1155/ES/2006/32192 """ On the considered computational platforms for operand lengths used in cryptogr

[issue37863] Speed up hash(fractions.Fraction)

Tim Peters added the comment: Some random notes: - 1425089352415399815 appears to be derived from using the golden ratio to contrive a worst case for the Euclid egcd method. Which it's good at :-) Even so, the current code runs well over twice as fast as when replacing the pow(that, -1, P

[issue37863] Speed up hash(fractions.Fraction)

Raymond Hettinger added the comment: There's likely more that could be done -- I've just taken the low hanging fruit. If someone wants to re-open this and go farther, please take it from here. -- resolution: -> fixed stage: patch review -> resolved status: open -> closed _

[issue37863] Speed up hash(fractions.Fraction)

Raymond Hettinger added the comment: New changeset f3cb68f2e4c3e0c405460f9bb881f5c1db70f535 by Raymond Hettinger in branch 'master': bpo-37863: Optimize Fraction.__hash__() (#15298) https://github.com/python/cpython/commit/f3cb68f2e4c3e0c405460f9bb881f5c1db70f535 -- ___

[issue37863] Speed up hash(fractions.Fraction)

Tim Peters added the comment: Mark, I did just a little browsing on this. It seems it's well known that egcd beats straightforward exponentiation for this purpose in arbitrary precision contexts, for reasons already sketched (egcd needs narrower arithmetic from the start, benefits from the

[issue37863] Speed up hash(fractions.Fraction)

Tim Peters added the comment: Well, details matter ;-) Division in Python is expensive. In the exponentiation algorithm each reduction (in general) requires a 122-by-61 bit division. In egcd, after it gets going nothing exceeds 61 bits, and across iterations the inputs to the division ste

[issue37863] Speed up hash(fractions.Fraction)

Mark Dickinson added the comment: > Indeed, I bet it would pay in `long_pow()` to add another test, under the `if > (Py_SIZE(b) < 0)` branch, to skip the exponentiation part entirely when b is > -1. Agreed. -- ___ Python tracker

[issue37863] Speed up hash(fractions.Fraction)

Mark Dickinson 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 i

[issue37863] Speed up hash(fractions.Fraction)

Tim Peters added the comment: Why I expected a major speedup from this: the binary exponentiation routine (for "reasonably small" exponents) does 30 * ceiling(exponent.bit_length() / 30) multiply-and-reduces, plus another for each bit set in the exponent. That's a major difference between

[issue37863] Speed up hash(fractions.Fraction)

Mark Dickinson added the comment: > Should be significantly faster. If not, the new "-1" implementation should > be changed ;-) I wouldn't have bet on this, before seeing Raymond's benchmark results. Writing a fast path for invmod for C-size integers is still on my to-do list; the current

[issue37863] Speed up hash(fractions.Fraction)

Raymond Hettinger added the comment: I make a quick PR for you. Skipped #1 because I don't think Fraction hashing is worth adding another slot. -- nosy: +mark.dickinson, rhettinger ___ Python tracker _

[issue37863] Speed up hash(fractions.Fraction)

Change by Raymond Hettinger : -- keywords: +patch pull_requests: +15021 stage: needs patch -> patch review pull_request: https://github.com/python/cpython/pull/15298 ___ Python tracker ___

[issue37863] Speed up hash(fractions.Fraction)

Change by ppperry : -- title: Speed hash(fractions.Fraction) -> Speed up hash(fractions.Fraction) ___ Python tracker ___ ___ Python-