Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.dougwise.org!aioe.org!news.glorb.com!news2.glorb.com!news-out.octanews.net!indigo.octanews.net!auth.beige.octanews.com.POSTED!not-for-mail From: Paul Rubin Newsgroups: comp.lang.python Subject: Re: integer multiplication References: Date: Sun, 03 Apr 2011 22:51:46 -0700 Message-ID: <7xy63qpnrh.fsf@ruckus.brouhaha.com> Organization: Nightsong/Fort GNOX User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux) Cancel-Lock: sha1:zacdDVX76Zlnp0xFuzUzbxngKVI= MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Lines: 19 NNTP-Posting-Date: 04 Apr 2011 00:51:46 CDT X-Complaints-To: abuse@octanews.net Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:2550 geremy condra 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.