[New-bugs-announce] [issue18005] faster modular exponentiation in some cases
Pernici Mario
report at bugs.python.org
Sat May 18 12:07:19 CEST 2013
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 <report at bugs.python.org>
<http://bugs.python.org/issue18005>
_______________________________________
More information about the New-bugs-announce
mailing list