New submission from Pernici Mario: A trivial optimization can be made in ``pow(a, b, c)`` if ``b`` is even and ``c - a < a``
``` In [1]: c = (1 << 1000000) + 1 In [2]: a = c - 1234567 In [3]: b = 2 In [4]: %timeit pow(a, b, c) 1 loops, best of 3: 3.03 s per loop In [5]: %timeit pow(c - a if c - a < (a >> 10) else a, b, c) 1000 loops, best of 3: 287 us per loop ``` This optimization is probably done in GMP, since using gmpy.mpz [5] is a bit slower than [4]. ---------- messages: 189504 nosy: pernici priority: normal severity: normal status: open title: faster modular exponentiation in some cases type: performance versions: Python 2.7 _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue18005> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
