FFT Lib?

[Don]

dsimcha wrote:
> == Quote from Fawzi Mohamed (fawzi at gmx.ch)'s article
>> On 29-lug-10, at 15:31, dsimcha wrote:
>>> == Quote from Fawzi Mohamed (fawzi at gmx.ch)'s article
>>>> otherwise, as I already said http://www.netlib.org/fftpack/fft.c is
>>>> public domain, has reasonable performance, and supports all sizes.
>>>> It might not be the always beautiful, but it is stable and works
>>>> well...
>>>> Fawzi
>>> Yeah, I just looked at this code.  The problem is that I wouldn't do
>>> a straight,
>>> mechanical port to D, I'd D-ify the code a little while I was at it
>>> (such as
>>> making it work on generic random access ranges if it's an out of
>>> place transform,
>>> making real-only inputs vs. complex inputs DRYer with templates,
>>> etc.).  Since
>>> this code seems to have been straight-up translated from FORTRAN, it
>>> scores about
>>> a -2 the readability scale, from 1 to 10.  In other words, I would
>>> probably be
>>> able to translate it and make it run, but even the slightest
>>> modification would be
>>> near impossible.
>> eheh this must meant that too much fortran inured me, I did not find
>> the code too bad, I classified it as a typical numerical intensive
>> code (even rather clean where one can easily find the boundaries of
>> the arrays, and without too many goto), and templating float, using
>> slices as input seemed easy.
> 
> Yes, but typical numerics intensive code is basically unreadable.  I think D is
> about the only language that has enough high-level stuff (templates, etc.) to
> write readable numerics code with a nice interface, but is also efficient enough
> to write efficient numerics code.  Unfortunately, we're basically starting from
> scratch because C and Fortran numerics code is so crufty and unreadable that it's
> really, really hard to refactor it into readable D or even put a nice interface on it.
> 
>> But yes probably it is not the best basis to develop your own thing.
>> Ahrg fortran ruined me ;).
>> ciao
>> Fawzi
> 
> I got permission from Mark Borgerding to port kissfft and have the binary
> attribution clause waived, but unfortunately this code is almost as difficult to
> read due to its extreme preprocessor abuse.  (Basically he implements complex
> numbers as a struct with an imaginary and real component and a bunch of
> preprocessor macros.)  Part of the preprocessor abuse is necessary for supporting
> fixed point FFTs.  Does anyone care about these (I sure don't), or can I just get
> rid of them?
> 
> I'm hoping I can refactor this code into a nice D interface, but it may end up
> being that I have to basically start from scratch.  One thing I will absolutely
> not do is contribute code without a proper D-style (i.e. templated, works with
> std.complex, etc.) interface.  If I can't understand kissfft well enough to do
> this refactoring, then maybe I'll just start from scratch using the Wikipedia FFT
> article and a textbook.

This is a useful read on FFT performance.
http://cnx.org/content/m16336/latest/