FFT Lib?

Fawzi Mohamed fawzi at gmx.ch
Thu Jul 29 00:38:10 PDT 2010


On 29-lug-10, at 00:01, dsimcha wrote:

> == Quote from jtravs (jtravs at gmail.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" over "has every
>>> micro-optimization in the book but a PITA to maintain/modify/use",  
>>> as long as
>>> it's at least a true fft as opposed to an O(N^2) DFT.  A few  
>>> questions:
>>>
>>> 1.  Does anyone already have such a lib?
>>>
>>> 2.  If noone has one I'll probably either write my own from  
>>> scratch  or port
>>> some code from C if I can find code that's under a suitable  
>>> license and
>>> written with a "simple and good enough" philosophy rather than an  
>>> "every tiny
>>> optimization in the book" philosophy.  Could anyone recommend one  
>>> to port?
>>>
>> You should have a look at kissfft. It is very small (one short c  
>> file),
> appropriately licensed and supports arbitrary sizes quite efficiently.
>> I have recently ported this to the go programming language in just  
>> a few hours
> work. I'm willing to help with a D version too, if you want, as I  
> might also need
> this soon.
>> kissfft can be found at: http://kissfft.sourceforge.net
>> J
>
> This looks great except that the license requires binary  
> attribution.  I've
> emailed the author and asked him to waive the binary attribution  
> requirement and
> let me use it under the Boost license for the purpose of a D port.   
> If he goes for
> it, I'll probably just port this code to D for std.numeric, and then  
> use it where
> I need to in dstats.  Otherwise, it's back to square 1.

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


More information about the Digitalmars-d mailing list