Subject: "fastfib" in the gf package faster than "fib"
From: Stavros Macrakis
Date: Tue, 8 Jul 2008 17:52:09 -0400
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