Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <ian.g.kelly@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.018
X-Spam-Evidence: '*H*': 0.96; '*S*': 0.00; 'numerical': 0.05; '"""': 0.07; 'python': 0.08; 'wed,': 0.12; 'wrote:': 0.15; 'billy': 0.16; 'core.': 0.16; 'algorithm': 0.16; 'pm,': 0.16; 'large,': 0.19; 'starts': 0.19; 'header:In-Reply-To:1': 0.22; 'libraries': 0.25; 'noticed': 0.26; 'beyond': 0.28; 'message-id:@mail.gmail.com': 0.28; 'wondering': 0.30; 'subject:number': 0.30; 'source': 0.32; 'implementing': 0.32; 'rather': 0.33; 'done': 0.33; 'to:addr :python-list': 0.34; 'there': 0.34; 'probably': 0.35; 'using': 0.37; 'received:google.com': 0.38; 'received:209.85.161': 0.38; 'received:209.85': 0.38; 'subject:: ': 0.38; 'think': 0.38; 'to:addr:python.org': 0.39; 'received:209': 0.40; 'chosen': 0.40; 'methods': 0.40; 'according': 0.63; 'benefit': 0.66; 'specialized': 0.71; '40,000': 0.84
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type:content-transfer-encoding; bh=2yxJtYMmqQxpZMP8bgtQlNPKjygn5aelJSaELaaq5UM=; b=CIX18+ehly2C3v+ojfL+4thMNF247GpY6H2M+EmtOUw561KjbbTTbgPirxOsEj80bG ph1jMGFgeKOVjEKrmBN+D6Vo6ZyD0Xa1i7RpZYefCVi++ly2q9GphLL8qxVae98qctmu vE9bnRopnyU+EkIBy7G9nUexpkUsaL0diUoak=
MIME-Version: 1.0
In-Reply-To: <iv2d7n$ksv$1@speranza.aioe.org>
References: <iv2d7n$ksv$1@speranza.aioe.org>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Wed, 6 Jul 2011 14:02:04 -0600
Subject: Re: Large number multiplication
To: Python <python-list@python.org>
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable
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.721.1309982555.1164.python-list@python.org>
Lines: 20
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1309982555 news.xs4all.nl 21775 [2001:888:2000:d::a6]:33459
X-Complaints-To: abuse@xs4all.nl
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:8981

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 multiplicat=
ion
> is done using the Karatsuba method (O(~n^1.5)) rather than using FFTs O(~=
n
> log n). =A0I was wondering if there was a reason the Karatsuba method was
> chosen over the FFT convolution method?

According to Wikipedia:

"""
In practice the Sch=F6nhage=96Strassen algorithm starts to outperform
older methods such as Karatsuba and Toom=96Cook multiplication for
numbers beyond 2**2**15 to 2**2**17 (10,000 to 40,000 decimal digits).
"""

I think most Python users are probably not working with numbers that
large, and if they are, they are probably using specialized numerical
libraries anyway, so there would be little benefit in implementing it
in core.