FFT Lib?

[Don]

dsimcha wrote:
> == Quote from Don (nospam at nospam.com)'s article
>> dsimcha wrote:
>>> I'm going to need an FFT library to perform some convolutions at some point
>>> soon.  Two absolute, non-negotiable requirements are that it be written in
>>> pure D and that it be Boost or compatibly (i.e. zlib or public domain)
>>> licensed.  I also prefer "simple and good enough"
>> What does "simple" mean?
>> If you're happy with lengths being restricted to powers of 2, it's
>> simple. Most of the complexity of something like FFTW comes from support
>> for arbitrary lengths.
> 
> Yeh, I only need powers of two.  I realize this isn't very hard because I wrote a
> prototype of it a while back.  However, this prototype would basically need to be
> rewritten b/c:
> 
> 1.  It only supports pure real inputs, meaning you can't use it to compute inverse
> FFTs.
> 
> 2.  I tried to write it using strides instead of rearranging the elements of the
> arrays, mostly because I was curious what effect this would have on performance.
> It turned out to be disastrous, presumably because it killed cache efficiency.

I believe that a moderately efficient cache-aware FFT could be made 
using simple blocking with the info from core.cpuid.