Author pernici
Recipients pernici
Date 2013-05-18.10:07:19
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1368871639.93.0.89718215484.issue18005@psf.upfronthosting.co.za>
In-reply-to
Content
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].
History
Date User Action Args
2013-05-18 10:07:19pernicisetrecipients: + pernici
2013-05-18 10:07:19pernicisetmessageid: <1368871639.93.0.89718215484.issue18005@psf.upfronthosting.co.za>
2013-05-18 10:07:19pernicilinkissue18005 messages
2013-05-18 10:07:19pernicicreate