Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!feeder1.cambriumusenet.nl!feed.tweaknews.nl!194.134.4.91.MISMATCH!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <python-python-list@m.gmane.org>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.004
X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'python': 0.08; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:80.91.229.12': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'received:lo.gmane.org': 0.09; 'rounding': 0.09; 'billy': 0.16; 'subtraction': 0.16; 'algorithm': 0.16; 'header:In-Reply-To:1': 0.22; 'noticed': 0.26; 'wondering': 0.30; 'subject:number': 0.30; 'source': 0.32; 'rather': 0.33; 'done': 0.33; 'to:addr:python-list': 0.34; 'header:X-Complaints-To:1': 0.34; 'header:User-Agent:1': 0.34; 'there': 0.34; 'uses': 0.35; 'addition,': 0.36; 'using': 0.37; 'received:org': 0.38; 'subject:: ': 0.38; 'header:Mime-Version:1': 0.39; 'to:addr:python.org': 0.39; 'chosen': 0.40; 'schrieb': 0.84
X-Injected-Via-Gmane: http://gmane.org/
To: python-list@python.org
From: Christian Heimes <lists@cheimes.de>
Subject: Re: Large number multiplication
Date: Wed, 06 Jul 2011 22:05:52 +0200
References: <iv2d7n$ksv$1@speranza.aioe.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Gmane-NNTP-Posting-Host: f048238058.adsl.alicedsl.de
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.17) Gecko/20110516 Lightning/1.0b2.102ipre2 Thunderbird/3.1.10
In-Reply-To: <iv2d7n$ksv$1@speranza.aioe.org>
X-Enigmail-Version: 1.1.2
OpenPGP: id=AD16AB1B; url=http://cheimes.de/heimes.asc
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.722.1309982770.1164.python-list@python.org>
Lines: 15
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1309982770 news.xs4all.nl 21888 [2001:888:2000:d::a6]:35794
X-Complaints-To: abuse@xs4all.nl
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:8982

Am 06.07.2011 21:30, schrieb Billy Mays:
> 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 Karatsuba algorithm uses just addition, subtraction and
multiplication, so you don't need to resort to floats and have no
rounding errors. On the other hand FFT are based on e, complex numbers
or trigonometric functions (=floats), which mean you'll get rounding errors.

We don't want rounding errors for large long multiplication.

Christian