integer multiplication

casevh casevh at
Mon Apr 4 21:18:55 CEST 2011

On Apr 4, 9:41 am, Terry Reedy <tjre... 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.)
>  >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.
> --
> Terry Jan Reedy

(Disclaimer: I'm the current maintainer of gmpy.)

A quick comparison between native integers and gmpy.mpz() on Python
3.2, 64-bit Linux and gmpy 1.14.

For multiplication of single digit numbers, native integers are faster
by ~25%. The breakeven threshold for multiplication occurs around 12
digits and by 20 digits, gmpy is almost 2x faster.

I've made some improvements between gmpy 1.04 and 1.14 to decrease the
overhead for gmpy operations. The breakeven point for older versions
will be higher so if you are running performance critical code with
older versions of gmpy, I'd recommend upgrading to 1.14.


More information about the Python-list mailing list