Path: g2news1.google.com!news4.google.com!feeder2.cambriumusenet.nl!feed.tweaknews.nl!193.141.40.65.MISMATCH!npeer.de.kpn-eurorings.net!npeer-ng0.de.kpn-eurorings.net!newsfeed.straub-nv.de!feeder.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Dann Corbit <dcor...@connx.com>
Newsgroups: sci.math.symbolic,sci.math
Subject: Re: maple is slow, pari gp even slower (on 1 topic)
Date: Mon, 18 Jan 2010 18:04:27 -0800
Organization: A noiseless patient Spider
Lines: 28
Message-ID: <MPG.25beb2e929d85b3e9896bc@news.eternal-september.org>
References: <31423165-2a11-456b-9523-706d48a03c29@e16g2000yqc.googlegroups.com> <170120101956064769%anniel@nym.alias.net.invalid> <d9ockrvqzb.fsf@ada0.ifam.uni-hannover.de> <180120100647216267%anniel@nym.alias.net.invalid> <fIidnWJhJbCwHsnWnZ2dnUVZ_sKdnZ2d@earthlink.com> <b2af0072-7996-42aa-ab2e-d90ea1e29054@f12g2000yqn.googlegroups.com> <4B55026D.2A375034@freenet.de>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 19 Jan 2010 02:05:58 +0000 (UTC)
Injection-Info: feeder.eternal-september.org; posting-host="s1nvOyg/Sn+a63BHm0iozg";
	logging-data="18659"; mail-complaints-to="ab...@eternal-september.org";	posting-account="U2FsdGVkX1+vBclLizfpb9ImLvCt/qURp+nmXlgNTzI="
User-Agent: MicroPlanet-Gravity/2.9.14
Cancel-Lock: sha1:NcLMvHMg8w/35ir7a8hzi6DKadI=

In article <4B55026D.2A375...@freenet.de>, cliclic...@freenet.de says...
> 
> plouffe schrieb:
> > 
> >  The problem I think is that the bignum package does not use Karatsuba
> >  algorithm to multiply big numbers.
> > 
> 
> The Karatsuba algorithm, being an n^1.585 algorithm, isn't very
> interesting for 10^6 decimal digits. Fast Fourier Transform gives rise
> to an n*log(n) algorithm, see the chapter on Less Numerical Algorithms
> in Numerical Recipes by Press, Teukolsky, Vetterling, Flannery.

If the Plouffe you are responding to is this one:
http://www.lacim.uqam.ca/~plouffe/
who is the author of this thing (among other things):
http://pi.lacim.uqam.ca/

then I guess he knows a lot about multiple precision mathamatics.

Be that as it may, ffts are usually used for very large precisions.  Not 
sure where Karatsuba coughs out and fft takes over, but surely by the 
millions of digits and probably by the tens of thousands for most 
implementations.

In any case, there appears to be a defect in the bignum package in use
(presumably, it is using the "schoolbook" algorithm for large 
precisions, which would be pretty awful.