www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - FFT Lib?

reply dsimcha <dsimcha yahoo.com> writes:
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?

3.  If I do end up writing my own or porting, is there sufficient interest in
this that I should try to target it for std.numerics, or would I be better off
just making it good enough for my use case?
Jul 27 2010
next sibling parent reply "Mike James" <foo bar.com> writes:
"dsimcha" <dsimcha yahoo.com> wrote in message 
news:i2na5q$2kgi$1 digitalmars.com...
 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?

 3.  If I do end up writing my own or porting, is there sufficient interest 
 in
 this that I should try to target it for std.numerics, or would I be better 
 off
 just making it good enough for my use case?

This is one of the best FFTs I've used... http://www.fftw.org/ I don't know whether the licence is ok for you. -=mike=-
Jul 27 2010
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Mike James (foo bar.com)'s article
 This is one of the best FFTs I've used...
 http://www.fftw.org/
 I don't know whether the licence is ok for you.
 -=mike=-

I was aware of this, but: 1. GPL 2. "every microoptimization", not "simple and good enough", so it would likely be a PITA to port. This doesn't matter anyhow, though, because of (1).
Jul 27 2010
prev sibling next sibling parent reply Rory Mcguire <rjmcguire gm_no_ail.com> writes:
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?
 
 3.  If I do end up writing my own or porting, is there sufficient interest
 in this that I should try to target it for std.numerics, or would I be
 better off just making it good enough for my use case?

Hi, I haven't used fft for anything before not sure what I'd use it for either, here is public domain code claiming to be a fft: http://www.dsprelated.com/showmessage/36380/1.php And here is a list of fft libs: http://fftw.org/benchfft/ffts.html -Rory
Jul 27 2010
next sibling parent reply Fawzi Mohamed <fawzi gmx.ch> writes:
On 27-lug-10, at 21:47, Rory Mcguire wrote:

 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?

 3.  If I do end up writing my own or porting, is there sufficient  
 interest
 in this that I should try to target it for std.numerics, or would I  
 be
 better off just making it good enough for my use case?

Hi, I haven't used fft for anything before not sure what I'd use it for either, here is public domain code claiming to be a fft: http://www.dsprelated.com/showmessage/36380/1.php And here is a list of fft libs: http://fftw.org/benchfft/ffts.html -Rory

I was preceded, that is a good list. I can only say that FFTW is *really* good, and if you structure your code well you should be able to support more than one library. I have wrappers for fftw, and it can be used with NArray (N dimensional dense arrays in blip), but is not directly there exactly due to the license. So having a fallback FFT would be useful for me. ciao Fawzi
Jul 27 2010
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Fawzi Mohamed (fawzi gmx.ch)'s article
 I was preceded, that is a good list. I can only say that FFTW is
 *really* good, and if you structure your code well you should be able
 to support more than one library.
 I have wrappers for fftw, and it can be used with NArray (N
 dimensional dense arrays in blip), but is not directly there exactly
 due to the license.
 So having a fallback FFT would be useful for me.
 ciao
 Fawzi

This was kind of my point: Does a "simple and good enough" FFT that's O(N log N) but not super optimized and maybe works on generic ranges and ranges of ranges belong in Phobos? The idea is that if you just need a few FFTs here and there, convenience is important, and they're not a major bottleneck for you, you use Phobos. If you need the absolute best even if it has to be installed separately, is under a more restrictive license, is more of a PITA to use, etc., you use FFTW or something. My use case, to give a little more detail as an example, is that I want to add kernel density estimation to dstats. I need a reasonably efficient way to compute a convolution, but not super-optimized pedal-to-the-metal ones, and I need to not have to add a dependency to dstats just for this and for the license to be compatible.
Jul 27 2010
prev sibling parent Fawzi Mohamed <fawzi gmx.ch> writes:
On 27-lug-10, at 23:28, dsimcha wrote:

 == Quote from Fawzi Mohamed (fawzi gmx.ch)'s article
 I was preceded, that is a good list. I can only say that FFTW is
 *really* good, and if you structure your code well you should be able
 to support more than one library.
 I have wrappers for fftw, and it can be used with NArray (N
 dimensional dense arrays in blip), but is not directly there exactly
 due to the license.
 So having a fallback FFT would be useful for me.
 ciao
 Fawzi

This was kind of my point: Does a "simple and good enough" FFT that's O(N log N) but not super optimized and maybe works on generic ranges and ranges of ranges belong in Phobos? The idea is that if you just need a few FFTs here and there, convenience is important, and they're not a major bottleneck for you, you use Phobos. If you need the absolute best even if it has to be installed separately, is under a more restrictive license, is more of a PITA to use, etc., you use FFTW or something.

about belonging to phobos I don't know, but it would be useful. The program I am working on will be GPL, so I don't have problems with fftw, still the fftw binding is one place where I know that I should work more...
 My use case, to give a little more detail as an example, is that I  
 want to add
 kernel density estimation to dstats.  I need a reasonably efficient  
 way to compute
 a convolution, but not super-optimized pedal-to-the-metal ones, and  
 I need to not
 have to add a dependency to dstats just for this and for the license  
 to be compatible.

I understand, I need more performance from the fft. I know numpy uses fftpack, but that is fortran, but it has a c version, probably not the best choice to have a maintanable code, but the .c version is small, see http://www.netlib.org/fftpack/ fawzi
Jul 27 2010
prev sibling next sibling parent reply Don <nospam nospam.com> writes:
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.
 3.  If I do end up writing my own or porting, is there sufficient interest in
 this that I should try to target it for std.numerics, or would I be better off
 just making it good enough for my use case?

I think that a basic power-of-2 FFT is simple enough, and sufficiently widely used to be worth including.
Jul 27 2010
next sibling parent Fawzi Mohamed <fawzi gmx.ch> writes:
On 28-lug-10, at 06:22, Don wrote:

 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.

and cache awarness..., but yes efficiently supporting arbitrary lengths is difficult.
 3.  If I do end up writing my own or porting, is there sufficient  
 interest in
 this that I should try to target it for std.numerics, or would I be  
 better off
 just making it good enough for my use case?

I think that a basic power-of-2 FFT is simple enough, and sufficiently widely used to be worth including.

Note that the fft from fftpack support arbitrary lengths (the efficiency decreases, but not so drastically). I would put something like that for "casual" use, so that one doesn't have to worry too much about sizes. If he needs something better then he should start to worry about it. For example one could have a routine returning the next "good" size, always increasing. Fawzi
Jul 28 2010
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Don (nospam 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"

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.
Jul 28 2010
parent Don <nospam nospam.com> writes:
dsimcha wrote:
 == Quote from Don (nospam 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"

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.
Jul 28 2010
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--001636c5c06d4efee5048c741f46
Content-Type: text/plain; charset=ISO-8859-1

  3.  If I do end up writing my own or porting, is there sufficient interest
 in
 this that I should try to target it for std.numerics, or would I be better
 off
 just making it good enough for my use case?

I think that a basic power-of-2 FFT is simple enough, and sufficiently widely used to be worth including.

You have my vote, David. As long as it does 2D FFT, it'll cover the vast majority of my own needs. And FFT is exactly the kind of things I need regularly, but only a few times a year. Having it in std.numerics would be excellent. Philippe --001636c5c06d4efee5048c741f46 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margi= n:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class=3D"im= "><br> <br> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p= x #ccc solid;padding-left:1ex"> 3. =A0If I do end up writing my own or porting, is there sufficient interes= t in<br> this that I should try to target it for std.numerics, or would I be better = off<br> just making it good enough for my use case?<br> </blockquote> <br></div> I think that a basic power-of-2 FFT is simple enough, and sufficiently wide= ly used to be worth including.<br> </blockquote></div><br><div>You have my vote, David. As long as it does 2D = FFT, it&#39;ll cover the vast majority of my own needs. And FFT is exactly = the kind of things I need regularly, but only a few times a year. Having it= in std.numerics would be excellent.</div> <div><br></div><div><br></div><div>Philippe</div> --001636c5c06d4efee5048c741f46--
Jul 28 2010