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

Groups > comp.lang.python > #8982

Re: Large number multiplication

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

Show key headers only | View raw

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

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