cpython: 6fcdd1657ee3 (original) (raw)

Mercurial > cpython

changeset 85982:6fcdd1657ee3

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\. Merged from 3.3. [#19171]

Tim Peters tim@python.org
date	Sat, 05 Oct 2013 16:55:38 -0500
parents	63a10c942b50(current diff)f34c59494420(diff)
children	94246efe2275
files	Objects/longobject.c
diffstat	1 files changed, 10 insertions(+), 4 deletions(-)[+] [-] Objects/longobject.c 14

line wrap: on

line diff

--- a/Objects/longobject.c +++ b/Objects/longobject.c @@ -3878,10 +3878,16 @@ long_pow(PyObject *v, PyObject *w, PyObj goto Done; }

```
   /* if base < 0:[](#l1.7)
```

          base = base % modulus[](#l1.8)

      Having the base positive just makes things easier. */[](#l1.9)

```
   if (Py_SIZE(a) < 0) {[](#l1.10)
```

   /* Reduce base by modulus in some cases:[](#l1.11)

      1. If base < 0.  Forcing the base non-negative makes things easier.[](#l1.12)

      2. If base is obviously larger than the modulus.  The "small[](#l1.13)

         exponent" case later can multiply directly by base repeatedly,[](#l1.14)

         while the "large exponent" case multiplies directly by base 31[](#l1.15)

         times.  It can be unboundedly faster to multiply by[](#l1.16)

         base % modulus instead.[](#l1.17)

      We could _always_ do this reduction, but l_divmod() isn't cheap,[](#l1.18)

      so we only do it when it buys something. */[](#l1.19)

   if (Py_SIZE(a) < 0 || Py_SIZE(a) > Py_SIZE(c)) {[](#l1.20)
       if (l_divmod(a, c, NULL, &temp) < 0)[](#l1.21)
           goto Error;[](#l1.22)
       Py_DECREF(a);[](#l1.23)