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

Groups > comp.lang.python > #2550

Re: integer multiplication

Show all headers | View raw

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.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web