FFT Lib?

[dsimcha]

== 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.