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


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.