integer multiplication

geremy condra debatem1 at
Mon Apr 4 13:20:16 EDT 2011

On Mon, Apr 4, 2011 at 9:41 AM, Terry Reedy <tjreedy at> wrote:
> On 4/4/2011 1:51 AM, Paul Rubin wrote:
>> I didn't realize Python used Karatsuba.  The main issue is probably that
>> Python uses a straightforward portable C implementation that's not
>> terribly efficient,
> but relatively easy for a couple of people to maintain. For (C)Python 3,
> which no longer has a C int type, I believe changes were focused on making
> calculations with small integers almost as fast as in 2.x.
> (I believe that retaining two implementations internally was considered but
> rejected. Could be wrong.)

There are two implementations, grade school multiplication and
karatsuba, which kicks in after a given cutoff.

>>If you look for the gmpy module, it gives you a way to use gmp from
>>Python.  In crypto code (lots of 1024 bit modular exponentials) I think
>>I found gmpy to be around 4x faster than Python longs.
> For specialized use, specialized gmpy is the way to go.
> I am curious how gmpy compares to 3.x ints (longs) with small number
> calculations like 3+5 or 3*5.

I have this data somewhere, if you're interested I'll try to dredge it up.

Geremy Condra

More information about the Python-list mailing list