Mark Dickinson <dicki...@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 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. ---------- Added file: http://bugs.python.org/file15703/long_pow_2009_12_30.diff _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue936813> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
