homepage

Just to be clear: this patch halves the number of shifts and masks, 
asymptotically; it doesn't affect the number of adds and multiplies 
(except for saving a few additions to zero by setting the initial carry 
intelligently). Is that correct? It's quite surprising that the bit 
operations have such a large effect on the running time.
Perhaps this is an argument for considering changing PyLong_SHIFT to 16 
(or better, 32, since surely almost every compiler provides uint64_t or 
equivalent these days)? Though that would be quite an involved task.
While I believe the idea is sound, the patch isn't quite correct---it's 
got some assertions that won't always hold. For example, with the 
patch, in a debug build of Python, I get:
>>> a = b = 2**30-1
[36413 refs]
>>> a*b
Assertion failed: (carry <= PyLong_MASK), function x_mul, file 
Objects/longobject.c, line 2228.
Abort trap
I'm fairly sure that the assert(carry <= PyLong_MASK) doesn't matter, 
and that the assertion at the end of the main outer loop (assert(carry 
>> PyLong_SHIFT) == 0)) should still hold. But some more comments and 
analysis in the code would be good. For example, if carry >= 
PyLong_MASK the the comment that 2*MASK + 2*MASK*MASK is contained in a 
twodigit isn't so useful. How big can carry get?