Re: Large number multiplication

Path	csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder2.enfer-du-nord.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path	<bounces@nabble.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.000
X-Spam-Evidence	'H': 1.00; 'S': 0.00; 'bits': 0.07; 'python': 0.08; "(it's": 0.09; 'alter': 0.09; 'context:': 0.09; 'graph': 0.09; 'wed,': 0.12; 'url:software': 0.13; 'wrote:': 0.15; '(best': 0.16; 'any)': 0.16; 'billy': 0.16; 'complexity,': 0.16; 'huge.': 0.16; 'message-id:@talk.nabble.com': 0.16; 'nabble.com.': 0.16; 'operands': 0.16; 'received:192.168.236': 0.16; 'received:192.168.236.156': 0.16; 'received:216.139': 0.16; 'received:216.139.236': 0.16; 'received:isper.nabble.com': 0.16; 'received:nabble.com': 0.16; 'url:nabble': 0.16; 'url:old': 0.16; 'pm,': 0.16; 'developer,': 0.19; 'simpler': 0.19; 'discussion': 0.22; 'header:In-Reply-To:1': 0.22; 'trying': 0.23; 'archive': 0.23; 'worked': 0.24; 'noticed': 0.26; "i'm": 0.27; 'guess': 0.28; 'attach': 0.28; 'wondering': 0.30; 'kelly': 0.30; 'marco': 0.30; 'subject:number': 0.30; 'yes.': 0.30; 'hi,': 0.31; 'source': 0.32; 'list': 0.32; 'rather': 0.33; 'done': 0.33; 'to:addr:python-list': 0.34; 'there': 0.34; 'algorithms': 0.35; 'latter': 0.35; 'uses': 0.35; '(with': 0.35; 'charset:us-ascii': 0.36; '(by': 0.37; 'some': 0.37; 'but': 0.37; 'using': 0.37; 'received:192': 0.38; 'url:org': 0.38; 'subject:: ': 0.38; 'execution': 0.38; 'size,': 0.38; 'mailing': 0.38; 'finding': 0.39; 'to:addr:python.org': 0.39; 'chosen': 0.40; 'view': 0.67; 'url:it': 0.68; 'timings': 0.84; '10000': 0.91; 'complexity': 0.93
Date	Thu, 7 Jul 2011 09:00:08 -0700 (PDT)
From	Parerga <nabble.com@bodrato.it>
To	python-list@python.org
Subject	Re: Large number multiplication
In-Reply-To	<iv2g6s$sl0$1@speranza.aioe.org>
MIME-Version	1.0
Content-Type	text/plain; charset=us-ascii
Content-Transfer-Encoding	7bit
X-Nabble-From	nabble.com@bodrato.it
References	<iv2d7n$ksv$1@speranza.aioe.org> <iv2g6s$sl0$1@speranza.aioe.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.749.1310054411.1164.python-list@python.org> (permalink)
Lines	51
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1310054411 news.xs4all.nl 21858 [2001:888:2000:d::a6]:44317
X-Complaints-To	abuse@xs4all.nl
Xref	x330-a1.tempe.blueboxinc.net comp.lang.python:9037

Show key headers only | View raw

Hi,


Billy Mays wrote:
> 
>> On 07/06/2011 04:02 PM, Ian Kelly wrote:
>> > On Wed, Jul 6, 2011 at 1:30 PM, Billy Mays<noway@nohow.com>  wrote:
>> >> I was looking through the python source and noticed that long
>> multiplication
>> >> is done using the Karatsuba method (O(~n^1.5)) rather than using FFTs
>> O(~n
>> >> log n).  I was wondering if there was a reason the Karatsuba method
>> was
>> >> chosen over the FFT convolution method?
> 
>> The reason I ask is because convolution has a better (best ?) complexity 
> 

Better complexity, yes. This means "smaller execution time for LARGE ENOUGH
operands"


Billy Mays wrote:
> 
>> I was more interested in finding previous discussion (if any) on why 
>> Karatsuba was chosen, not so much as trying to alter the current 
>> multiplication implementation.
> 

I'm not a python developer, but I worked on multiplication algorithms for
GMP  [ http://gmplib.org/ ], and I can guess the answer:
 - Karatsuba is (by far) simpler to implement,
 - FFT-based multiplication is (by far) slower than Karatsuba for numbers
that are not huge.
I try to attach a small graph 
http://old.nabble.com/file/p32014454/karaVSfft.pdf karaVSfft.pdf , with
timings for multiplications of n-bits operands (with GMP, on my very old
laptop) with Toom(2,2) (it's Karatsuba!) and the FFT-based computation. The
first is faster than the latter up to 10000 bits (GMP uses some Toom for
that size, to get the result even faster).

Regards,
Marco

--
http://bodrato.it/software/toom.html
-- 
View this message in context: http://old.nabble.com/Large-number-multiplication-tp32007815p32014454.html
Sent from the Python - python-list mailing list archive at Nabble.com.

Thread

Large number multiplication Billy Mays <noway@nohow.com> - 2011-07-06 15:30 -0400
  Re: Large number multiplication Ian Kelly <ian.g.kelly@gmail.com> - 2011-07-06 14:02 -0600
    Re: Large number multiplication Billy Mays <noway@nohow.com> - 2011-07-06 16:21 -0400
      Re: Large number multiplication Ian Kelly <ian.g.kelly@gmail.com> - 2011-07-06 14:37 -0600
      Re: Large number multiplication Ulrich Eckhardt <ulrich.eckhardt@dominolaser.com> - 2011-07-07 10:30 +0200
        Re: Large number multiplication Ian Kelly <ian.g.kelly@gmail.com> - 2011-07-07 09:49 -0600
        Re: Large number multiplication Ian Kelly <ian.g.kelly@gmail.com> - 2011-07-07 09:50 -0600
        Re: Large number multiplication casevh <casevh@gmail.com> - 2011-07-07 10:46 -0700
        Re: Large number multiplication Mark Dickinson <mdickinson@enthought.com> - 2011-07-08 00:31 -0700
      Re: Large number multiplication Parerga <nabble.com@bodrato.it> - 2011-07-07 09:00 -0700
  Re: Large number multiplication Christian Heimes <lists@cheimes.de> - 2011-07-06 22:05 +0200
    Re: Large number multiplication Billy Mays <noway@nohow.com> - 2011-07-06 16:15 -0400
      Re: Large number multiplication Christian Heimes <lists@cheimes.de> - 2011-07-06 22:43 +0200
    Re: Large number multiplication Nobody <nobody@nowhere.com> - 2011-07-07 01:33 +0100

csiph-web