FFT Lib?

[Mike James]

"dsimcha" <dsimcha at yahoo.com> wrote in message 
news:i2umov$2esa$1 at digitalmars.com...
> == 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?

Fixed-point FFTs could be important if your number-crunching data that could 
have been collected by, say, a microcontroller-based system with 16-bit 
ADCs. Integer-only FFTs are useful.

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