[issue4258] Use 30-bit digits instead of 15-bit digits for Python integers.

Mark Dickinson report at bugs.python.org
Tue Nov 11 17:31:00 CET 2008


Mark Dickinson <dickinsm at gmail.com> added the comment:

Here's a version of the 15-bit to 30-bit patch
that adds in a souped-up version of Mario Pernici's
faster multiplication.

I did some testing of 100x100 digit and 1000x1000 digit
multiplies.  On 32-bit x86:
  100 x 100 digits  : around 2.5 times faster
 1000 x 1000 digits : around 3 times faster.

On x86_64, I'm getting more spectacular results:
  100 x 100 digits : around 5 times faster
 1000 x 1000 digits: around 7 times faster!

The idea of the faster multiplication is quite simple:
with 30-bit digits, one can fit a sum of 16 30-bit by
30-bit products in a uint64_t.  This means that the
inner loop for the basecase grade-school multiplication
contains one fewer addition and no mask and shift.

[Victor, please don't delete the old longdigit4.patch!]

Added file: http://bugs.python.org/file11986/30bit_longdigit6.patch

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue4258>
_______________________________________


More information about the Python-bugs-list mailing list