[Maxima] "fastfib" in the gf package faster than "fib"

[Raymond Toy (RT/EUS)]

Stavros Macrakis wrote:
> 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

Thanks for the pointer.  I was only familiar with the floating-point 
version.

Ray