"fastfib" in the gf package faster than "fib"

Thanks for pointing this out to me, the article was very interesting.  I don't think anything I want to do with Maxima requires more that a few hundred digits though.  I choose 500 a lot for fpprec when working with power series, that is usually good enough.

Rich




 ------------Original Message------------
From: "Stavros Macrakis" <macrakis at alum.mit.edu>
To: "Raymond Toy (RT/EUS)" <raymond.toy at ericsson.com>
Cc: "Richard Hennessy" <rvh2007 at comcast.net>, "Maxima List" <maxima at math.utexas.edu>
Date: Tue, Jul-8-2008 5:52 PM
Subject: Re: [Maxima] "fastfib" in the gf package faster than "fib"

On Tue, Jul 8, 2008 at 4:44 PM, Raymond Toy (RT/EUS)
<raymond.toy at ericsson.com> wrote:
> Stavros Macrakis wrote:
>>
>> By the way, the n*log(n) algorithm you're probably thinking of,
>> Sch?nhage-Strassen (actually O(n*log(n)*log(log(n))), has a crossover
>>>> (http://en.wikipedia.org/wiki/Sch%C3%B6nhage-Strassen_algorithm).
>
> Isn't an FFT multiplier n*log(n)?  I think that FFT has 2 cross-overs
> because it's faster if the numbers are big enough, but you can't go
> arbitrarily large because the FFT is usually floating-point, so you have to
> be careful with roundoff.

Schoenhage-Strassen *is* the usual n*log(n)*log(log(n)) FFT-based
algorithm, but it uses FFTs in finite rings; no floating-point, no
roundoff.  And that really *is* its asymptotic behavior.  There is no
second crossover back!! The wikipedia article I pointed to is good
background.

             -s