Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder1.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: <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.021
X-Spam-Evidence: '*H*': 0.96; '*S*': 0.00; 'classes.': 0.05; 'python': 0.08; 'longs': 0.09; '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; 'fpu': 0.16; 'version).': 0.16; "haven't": 0.21; 'header:In-Reply-To:1': 0.22; "i'm": 0.27; 'guess': 0.28; 'subject:number': 0.30; 'does': 0.32; 'implement': 0.33; 'to:addr :python-list': 0.34; 'header:X-Complaints-To:1': 0.34; 'header :User-Agent:1': 0.34; 'there': 0.34; 'points': 0.34; 'integer': 0.35; 'error.': 0.36; 'familiar': 0.36; 'unless': 0.37; 'platforms': 0.37; 'but': 0.37; 'using': 0.37; 'received:org': 0.38; 'subject:: ': 0.38; 'think': 0.38; 'run': 0.39; 'header :Mime-Version:1': 0.39; 'to:addr:python.org': 0.39; 'might': 0.39; 'missing': 0.40; 'prevent': 0.40; 'double': 0.62; 'believe': 0.66; 'skip:1 10': 0.66; 'learned': 0.73; 'introduce': 0.79; 'floats.': 0.84; 'numerics': 0.84; 'schrieb': 0.84; 'involved.': 0.91
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:43:04 +0200
References: <iv2d7n$ksv$1@speranza.aioe.org>	<mailman.722.1309982770.1164.python-list@python.org> <iv2frn$rte$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: <iv2frn$rte$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.725.1309984999.1164.python-list@python.org>
Lines: 20
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1309984999 news.xs4all.nl 21867 [2001:888:2000:d::a6]:60480
X-Complaints-To: abuse@xs4all.nl
Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:8987

Am 06.07.2011 22:15, schrieb Billy Mays:
> I believe it is possible to do FFTs without significant rounding error. 
>   I know that the GIMPS's Prime95 does very large multiplications using 
> FFTs (I don't know if they use the integer based or double based 
> version).  I also know they have guards to prevent rounding errors so I 
> don't think it would be impossible to implement.

It might work for medium large longs but how about really large longs
like 5 * 1,000**10,000? I'm not familiar with FFT based multiplication
but I guess that very large numbers are going to introduce rounding
errors if floating points are involved.

Python used to run on platforms without an FPU and floats. These days
Python might still run on platforms with just an emulated FPU. Unless
there is a way to implement FFT without floating point ops, an emulated
or missing FPU makes FFT slower than Karatsuba. There might be one but I
haven't learned a way in my numerics classes.

Christian