Message from discussion maple is slow, pari gp even slower (on 1 topic)
From: Dann Corbit <dcor...@connx.com>
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
References: <email@example.com> <firstname.lastname@example.org> <email@example.com> <firstname.lastname@example.org> <fIidnWJhJbCwHsnWnZ2dnUVZ_sKdnZ2d@earthlink.com> <email@example.com> <4B55026D.2A375034@freenet.de>
Content-Type: text/plain; charset="us-ascii"
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="
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:
who is the author of this thing (among other things):
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
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.