Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #8981

Re: Large number multiplication

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> (permalink)
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

Show key headers only | View raw

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?

According to Wikipedia:

"""
In practice the Schönhage–Strassen algorithm starts to outperform
older methods such as Karatsuba and Toom–Cook 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.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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