Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #2541 > unrolled thread

Re: integer multiplication

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: integer multiplication geremy condra <debatem1@gmail.com> - 2011-04-03 18:33 -0700
    Re: integer multiplication Paul Rubin <no.email@nospam.invalid> - 2011-04-03 22:51 -0700
      Re: integer multiplication Terry Reedy <tjreedy@udel.edu> - 2011-04-04 12:41 -0400
        Re: integer multiplication casevh <casevh@gmail.com> - 2011-04-04 12:18 -0700
      Re: integer multiplication geremy condra <debatem1@gmail.com> - 2011-04-04 10:20 -0700
      Re: integer multiplication Terry Reedy <tjreedy@udel.edu> - 2011-04-04 15:04 -0400

#2541 — Re: integer multiplication

On Sun, Apr 3, 2011 at 6:20 PM, Eddie Tsay <jianyu44@gmail.com> wrote:
> Does anyone know what algorithms for integer multiplication does Python use?
> I am trying to compare it to those used by Sage as it seems like it takes
> much longer for Python to do large integer multiplication as compared to
> Sage (anyone know off the top of their heads?)
> thank you

(sorry for the double email, this was supposed to go to the list)

Karatsuba multiplication, at least for large integers.

Geremy Condra

[toc] | [next] | [standalone]

#2550

geremy condra <debatem1@gmail.com> writes:
>> Does anyone know what algorithms for integer multiplication does Python use?
>> I am trying to compare it to those used by Sage as it seems like it takes
>> much longer for Python to do large integer multiplication as compared to
>> Sage (anyone know off the top of their heads?)
>> thank you
> Karatsuba multiplication, at least for large integers.

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, while Sage might use something like GMP, which uses
carefully tuned assembler code on many processors.  

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.

I think for VERY big integers, GMP uses an FFT-based method that's
even faster than Karatsuba.

[toc] | [prev] | [next] | [standalone]

#2576

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

[toc] | [prev] | [next] | [standalone]

#2588

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

casevh

[toc] | [prev] | [next] | [standalone]

#2579

On Mon, Apr 4, 2011 at 9:41 AM, Terry Reedy <tjreedy@udel.edu> 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

[toc] | [prev] | [next] | [standalone]

#2583

On 4/4/2011 1:20 PM, geremy condra wrote:
> On Mon, Apr 4, 2011 at 9:41 AM, Terry Reedy<tjreedy@udel.edu>  wrote:

>> (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.

I meant internally retaining the 2.7 machine int and unbounded long types.

>> 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.

My question is whether gmpy ints could be a complete substitute for 3.x 
ints, or whether speed for bit (1000 digit) ints came at the expense of 
extra overhead making small int calculations slower. That is separate 
from the issue of whether gmpy ints implement the entire int interface, 
or whether they currently inter-operate with other types as well.

-- 
Terry Jan Reedy

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web