Tim Peters <t...@python.org> 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 exponents of bit lengths 61 ((P-2).bit_length()) and 1 ((1).bit_length()). 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. `long_invmod()` would be the end of it then. Because I expect using an exponent of -1 for modular inverse will be overwhelmingly more common than using any other negative exponent with a modulus. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue37863> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
