[issue936813] fast modular exponentiation
report at bugs.python.org
Wed Dec 30 20:02:43 CET 2009
Mark Dickinson <dickinsm at gmail.com> added the comment:
Here's a slightly modified version of Trevor's patch:
- update to apply cleanly to trunk
- fix misplaced twodigits cast described above
- add 'PyLong_' prefix to BASE, MASK and SHIFT
- no need for _PyLong_Copy in l_invmod: just copy and INCREF the
- don't calculate d - q*c by hand in l_invmod, since l_divmod computes
the remainder already
- simplify reference counting in l_invmod
- add a '* 1U' to a digit-by-digit multiplication, to avoid possible
(in theory; unlikely in practice) undefined behaviour resulting
from signed integer overflow.
The rest of the patch looks fine to me, modulo some minor style issues.
- it seems that l_invmod is only ever used to compute the inverse of a
single-digit long modulo PyLong_BASE. Mightn't it be more efficient to
simply do a twodigit/digit-based calculation here instead, to reduce the
overhead of setting up the Montgomery reductions?
- the current algorithm for three-argument pow involves many allocations
and deallocations of integers; it seems to me that these could almost
all be eliminated: for pow(a, b, c) with c an n-digit PyLong, just
allocate 2*n (or possibly 2*n+1) digits of workspace to begin with and
use that to store intermediate products; the Montgomery reduction could
then be done more-or-less in place. This doesn't work with the non-
Montgomery method, though, since l_divmod doesn't operate in place.
Added file: http://bugs.python.org/file15703/long_pow_2009_12_30.diff
Python tracker <report at bugs.python.org>
More information about the Python-bugs-list