On Thu, Apr 19, 2007 at 09:20:36 -0700, David Roundy wrote:

On Thu, Apr 19, 2007 at 05:37:05PM +0200, Fawzi Mohamed wrote:

...

I was wondering if someone had fftw bindings for haskell, or if I should roll my own.

Not that I'm aware of, but if you roll your own, please make them public, as I'll be interested in fftw bindings before long.

For us less knowledgable, what's fftw? /M (curious) -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus@therning.org Jabber: magnus.therning@gmail.com http://therning.org/magnus

On Thu, Apr 19, 2007 at 05:46:49PM -0400, Al Falloon wrote:

...

For us less knowledgable, what's fftw?

"Fastest Fourier Transform in the West." http://www.fftw.org/

Its cool, they use generative programming: an OCaml program generates "codlets" in C that can be composed and tuned to the specifics of your machine, then compiled into a blazingly fast FFT/DFT library.

But that's only the beginning of the coolness! fftw uses runtime timings to optimize each fourier transform based on the behavior of the computer on which it is being run--its cache, memory speed, CPU, etc. The result being that fftw using portable C can beat out most hand-optimized fftw libraries written in assembly! Steven (one of fftw's two authors) has done some incredible work on optimizations. The most unbelievable (to me) was that by eliminating negative constants from the generated code (using subtraction instead) they sped up the library on a particular architecture by some some significant margin (I think I recall 20%). -- David Roundy http://www.darcs.net

Christian Jaeger wrote:

Are you aware of Dan J. Bernstein's library?: http://cr.yp.to/djbfft.html

According to his benchmarks (from 1999?) it is faster than FFTW.

Quite possibly faster, but restricted to Intel and AMD CPUs. FFTW compiles and runs on anything with a C compiler. Erik -- +-----------------------------------------------------------+ Erik de Castro Lopo +-----------------------------------------------------------+ "Every time an American goes to a gas station, he is sending money to America's enemies." -- http://www.meforum.org/article/653

Thanks to everybody for the answers, For the moment I think that I will try to slightly expand http://ofb.net/~wnoise/haskell/FFTW/ that was pointed out to me by Patrik Sellin with respect to Dan J. Bernstein's library http://cr.yp.to/djbfft.html I was not aware of it, but I would like to have also non power of 2 grids... so FFTW. Fawzi

On Thu, Apr 19, 2007 at 05:46:49PM -0400, Al Falloon wrote:

...

...

For us less knowledgable, what's fftw?

"Fastest Fourier Transform in the West." http://www.fftw.org/

Its cool, they use generative programming: an OCaml program generates "codlets" in C that can be composed and tuned to the specifics of your machine, then compiled into a blazingly fast FFT/DFT library.

But that's only the beginning of the coolness! fftw uses runtime timings to optimize each fourier transform based on the behavior of the computer on which it is being run--its cache, memory speed, CPU, etc. The result being that fftw using portable C can beat out most hand-optimized fftw libraries written in assembly! Steven (one of fftw's two authors) has done some incredible work on optimizations. The most unbelievable (to me) was that by eliminating negative constants from the generated code (using subtraction instead) they sped up the library on a particular architecture by some some significant margin (I think I recall 20%). -- David Roundy

Oleg has some related work http://okmij.org/ftp/Computation/Generative.html#framework "... The papers discuss in detail the generation of a straight-line C, Fortran, etc. code for the power-of-two FFT. The papers show that with the help of Abstract Interpretation we can exactly match the quality of code generated by the well-known system FFTW. The second paper demonstrates that our generated power-of-two FFT code has exactly the same number of floating-point operations as that in codelets of FFTW. The significant difference from FFTW is that we do not do any intensional code analysis ... " I don't know how useful this is. Alistair ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************