Subject: "fastfib" in the gf package faster than "fib"
From: Raymond Toy (RT/EUS)
Date: Tue, 08 Jul 2008 16:44:51 -0400
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