classification
Title: faster modular exponentiation in some cases
Type: performance Stage:
Components: Versions: Python 3.4
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: Aaron.Meurer, eric.smith, lemburg, mark.dickinson, pernici, rhettinger, serhiy.storchaka, stutzbach
Priority: normal Keywords:

Created on 2013-05-18 10:07 by pernici, last changed 2013-06-04 15:46 by Aaron.Meurer. This issue is now closed.

Messages (2)
msg189504 - (view) Author: Pernici Mario (pernici) Date: 2013-05-18 10:07
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].
msg189505 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2013-05-18 11:13
Sorry, I'm rejecting this.  This sort of micro-optimization for a little-used operation doesn't belong in Python.  For applications that need it, use gmpy2.
History
Date User Action Args
2013-06-04 15:46:44Aaron.Meurersetnosy: + Aaron.Meurer
2013-05-18 11:13:15mark.dickinsonsetstatus: open -> closed
resolution: rejected
messages: + msg189505
2013-05-18 10:36:49serhiy.storchakasetnosy: + lemburg, rhettinger, mark.dickinson, eric.smith, stutzbach, serhiy.storchaka

versions: + Python 3.4, - Python 2.7
2013-05-18 10:07:19pernicicreate