Thanks for those results, Collin.

> By benchmark should be reproduced on a 64 bits CPU with 2^15 and 2^30
> bases for the long type.

On OS X 10.6 (64-bit Python non-debug non-framework build with gcc 4.2 
from Apple, 30-bit long digits, straight ./configure && make), Victor's 
benchmark gives me the following results:

original = 1023.9 ms  (best of 10 runs)
patched = 1005.3 ms (best of 10 runs).

- a speedup of about 1.85%.  So it looks as though x86_64 doesn't benefit 
to the same extent that 32-bit does.  Presumably that's because gcc-4.2 is 
unable or unwilling to turn a 64-bit by 64-bit division with a constant 
dividend of 10**9 into a multiplication;  I don't know whether using a 
later gcc would make a difference.