Re: integer multiplication

Path	csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.dougwise.org!gegeweb.org!de-l.enfer-du-nord.net!feeder2.enfer-du-nord.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed5.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path	<debatem1@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.002
X-Spam-Evidence	'H': 1.00; 'S': 0.00; 'int': 0.05; 'terry': 0.07; 'type,': 0.07; 'python': 0.07; '3.x': 0.09; 'compares': 0.09; 'integers': 0.09; 'internally': 0.09; 'rejected.': 0.09; 'am,': 0.14; 'wrote:': 0.14; '1024': 0.16; '>>i': 0.16; 'reedy': 0.16; '\xa0in': 0.16; 'cc:no real name:20': 0.20; 'cc:20': 0.20; 'code': 0.22; 'header:In-Reply-To:1': 0.22; 'cc:addr:python-list': 0.22; 'mon,': 0.22; 'curious': 0.23; 'module,': 0.23; 'retaining': 0.23; "didn't": 0.25; "i'll": 0.26; 'message-id:@mail.gmail.com': 0.28; 'changes': 0.29; 'probably': 0.30; 'up.': 0.30; 'cc:addr:python.org': 0.31; 'kicks': 0.31; 'paul': 0.32; 'go.': 0.33; 'relatively': 0.33; 'bit': 0.33; 'uses': 0.34; 'there': 0.35; 'couple': 0.35; 'received:209.85.216.46': 0.35; 'received :mail-qw0-f46.google.com': 0.35; 'think': 0.36; 'considered': 0.36; 'data': 0.37; 'two': 0.37; 'received:209.85': 0.37; 'issue': 0.37; 'apr': 0.38; 'faster': 0.38; 'received:google.com': 0.38; 'but': 0.38; 'used': 0.38; 'focused': 0.39; 'realize': 0.39; 'could': 0.39; 'received:209': 0.39; 'how': 0.39; 'header:Received:5': 0.40; 'specialized': 0.60; '2011': 0.62; 'making': 0.62; 'believe': 0.66; 'grade': 0.84; 'terribly': 0.84
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=Md7juwRDjSSlB7QXtTqjUrwK3UN7itUs+7CHucmk5as=; b=HySxvh6/PR5d8izTe5RrMtQZ8pqwSErZdVNrr/A5F/ImOhl5wYHjZz2Zzs6CLXZZUX jv7NnNePaa4aG58YiWwQEQVBwMZBnyabBFELW2ThFHkglwwjVSLNY5mzcz5iEQNjVUQs /XZ8sr7uB5YqCge/smzzk1QEqfuNsPN4RwIms=
DomainKey-Signature	a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; b=QZkNug3Nukus7BeZFHO0CFdoqCCXymI+b/m86BIt8ApmY8rGKRnjLX212mR+KkZiS9 KUIcAiVlBV+oHhnsa5KmBgiZoQfy4D8dsVhqfDU/6p7lsSrFPIvyfY8A72sEhmSOVpXK to0VYQ6SBfrNj48hXjpdTXq2k79L/f+oXF0oc=
MIME-Version	1.0
In-Reply-To	<incsbs$6b9$1@dough.gmane.org>
References	<BANLkTik5Oq0AE5-yrbSa2oES5_g8+gspeA@mail.gmail.com> <mailman.177.1301880825.2990.python-list@python.org> <7xy63qpnrh.fsf@ruckus.brouhaha.com> <incsbs$6b9$1@dough.gmane.org>
Date	Mon, 4 Apr 2011 10:20:16 -0700
Subject	Re: integer multiplication
From	geremy condra <debatem1@gmail.com>
To	Terry Reedy <tjreedy@udel.edu>
Content-Type	text/plain; charset=ISO-8859-1
Content-Transfer-Encoding	quoted-printable
Cc	python-list@python.org
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.12
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.12.1301937619.9059.python-list@python.org> (permalink)
Lines	32
NNTP-Posting-Host	82.94.164.166
X-Trace	1301937619 news.xs4all.nl 34849 [::ffff:82.94.164.166]:40553
X-Complaints-To	abuse@xs4all.nl
Xref	x330-a1.tempe.blueboxinc.net comp.lang.python:2579

Show key headers only | View raw

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

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