summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTim Peters <tim@python.org>2013-10-05 16:53:52 -0500
committerTim Peters <tim@python.org>2013-10-05 16:53:52 -0500
commit81a93159d7a4bfc6a6d06f44528d9d17a8c634c2 (patch)
tree02edb29d74df1369a2b1da0ea1552e875e8dfc85
parent7760b4eb4bedba81eb69d14f98ac978d37bc691a (diff)
downloadcpython-git-81a93159d7a4bfc6a6d06f44528d9d17a8c634c2.tar.gz
Issue #19171: speed some cases of 3-argument long pow().
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.
-rw-r--r--Objects/longobject.c14
1 files changed, 10 insertions, 4 deletions
diff --git a/Objects/longobject.c b/Objects/longobject.c
index 985b1ec83c..6383507a5c 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -3868,10 +3868,16 @@ long_pow(PyObject *v, PyObject *w, PyObject *x)
goto Done;
}
- /* if base < 0:
- base = base % modulus
- Having the base positive just makes things easier. */
- if (Py_SIZE(a) < 0) {
+ /* Reduce base by modulus in some cases:
+ 1. If base < 0. Forcing the base non-negative makes things easier.
+ 2. If base is obviously larger than the modulus. The "small
+ exponent" case later can multiply directly by base repeatedly,
+ while the "large exponent" case multiplies directly by base 31
+ times. It can be unboundedly faster to multiply by
+ base % modulus instead.
+ We could _always_ do this reduction, but l_divmod() isn't cheap,
+ so we only do it when it buys something. */
+ if (Py_SIZE(a) < 0 || Py_SIZE(a) > Py_SIZE(c)) {
if (l_divmod(a, c, NULL, &temp) < 0)
goto Error;
Py_DECREF(a);