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

[Raymond Toy (RT/EUS)]

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
>>> 10^10000. (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.  When numbers get really big, you have to 
switch to some other method.

Ray