Reduce the base by the modulus when the base is larger than
the modulus. This can unboundedly speed the "startup costs"
of doing modular exponentiation, particularly in cases where
the base is much larger than the modulus. Original patch
by Armin Rigo, inspired by https://github.com/pyca/ed25519.
(grafted from f34c59494420765b013136ca93f63b716d9f1d30)
(the latter renamed to _PyLong_Frexp) now use the same core code. The
exponent produced by _PyLong_Frexp now has type Py_ssize_t instead of the
previously used int, and no longer needs scaling by PyLong_SHIFT. This
frees the math module from having to know anything about the PyLong
implementation. This closes issue #5576.
(high_bits << PyLong_SHIFT) + low_bits with
(high_bits << PyLong_SHIFT) | low_bits
in Objects/longobject.c. Motivation:
- shouldn't unnecessarily mix bit ops with arithmetic ops (style)
- this pattern should be spelt the same way thoughout (consistency)
- it's very very very slightly faster: no need to worry about
carries to the high digit (nano-optimization).
correctly rounded, using round-half-to-even. This ensures that the
value of float(n) doesn't depend on whether we're using 15-bit digits
or 30-bit digits for Python longs.
