[issue936813] fast modular exponentiation

Mark Dickinson report at bugs.python.org
Thu Dec 31 20:39:36 CET 2009


Mark Dickinson <dickinsm at gmail.com> added the comment:

Okay, I retested the original patch without any of my refactoring (besides 
fixing the twodigits cast), and got pretty much the same numbers.

On a 32-bit non-debug trunk build (still on OS X 10.6), I get:

Unpatched
---------

Mark-Dickinsons-MacBook-Pro:trunk dickinsm$ ./python.exe 
../pow_benchmark.py 
1024 bits: 0.033691
2048 bits: 0.224796
3072 bits: 0.712510
4096 bits: 1.691484
Mark-Dickinsons-MacBook-Pro:trunk dickinsm$ ./python.exe ../time_powmod.py
64-bit modulus: 0.000054
253-bit modulus: 0.000981
1023-bit modulus: 0.034314

Patched
-------

Mark-Dickinsons-MacBook-Pro:trunk-issue936813 dickinsm$ ./python.exe 
../pow_benchmark.py 
1024 bits: 0.027317  (+23.3%)
2048 bits: 0.181053  (+24.2%)
3072 bits: 0.571688  (+24.6%)
4096 bits: 1.251051  (+35.2%)
Mark-Dickinsons-MacBook-Pro:trunk-issue936813 dickinsm$ ./python.exe 
../time_powmod.py
64-bit modulus: 0.000045 (+20.0%)
253-bit modulus: 0.000773 (+26.9%)
1023-bit modulus: 0.026983 (+27.2%)

I must admit I was hoping for a bit more than this.  IMO, these speedups 
aren't big enough to justify the extra complexity for what's really a bit 
of a niche function, so I'm going to reject this 3rd part and close this 
issue (but marking it as 'accepted' because most of the original 2004 
patch went in).

----------
resolution:  -> accepted
stage: patch review -> committed/rejected
status: open -> closed

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue936813>
_______________________________________


More information about the Python-bugs-list mailing list