Message97054
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
pointers
- 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.
Two points:
- 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. |
|
Date |
User |
Action |
Args |
2009-12-30 19:02:43 | mark.dickinson | set | recipients:
+ mark.dickinson, tim.peters, gregory.p.smith, trevp, christian.heimes |
2009-12-30 19:02:43 | mark.dickinson | set | messageid: <1262199763.41.0.954668388987.issue936813@psf.upfronthosting.co.za> |
2009-12-30 19:02:41 | mark.dickinson | link | issue936813 messages |
2009-12-30 19:02:40 | mark.dickinson | create | |
|