3

I'm looking for an FFT library to translate into the D programming language for inclusion either in a library that I'm working on or (better yet) in the standard library. I need a fairly simple FFT with decent performance, not an uber-optimized one with blazing fast performance and zero simplicity/readability. However, it must meet the following requirements:

  1. Either written in pure D or simple enough to be reasonably translatable to pure D. For example, readable C code without any inline assembler or preprocessor abuse would work. (I'm aware that you can call C from D, but I have my reasons for not wanting to.)

  2. Licensed under terms that are free/open-source, non-copyleft (i.e. not GPL) and do not require attribution for binary-only distribution (i.e. not BSD). Acceptable licenses include Boost, zlib and public domain.

  3. The code must be readable enough that I can sanely modify it to give it a nice D interface. I do not want super-optimized but unreadable Fortran code from the '70s, no matter how well it works. I also don't want C code that was translated from super-optimized Fortran code and looks like Fortran code.

Please do not suggest FFTW no matter how good it is (I understand it's very good), as it's both GPL licensed and written for performance over simplicity.

dsimcha
  • 67,514
  • 53
  • 213
  • 334
  • 1
    What's wrong with a license that requires attribution, like MIT or (3-clause) BSD? All it takes is a line somewhere in the About or documentation that says "libfftoo (c) Random Person". – ShreevatsaR Jul 31 '10 at 03:29
  • 2
    Or why not implement it yourself? The idea's fairly simple: http://stackoverflow.com/questions/3224823/how-exactly-do-you-compute-the-fast-fourier-transform/3226672#3226672 and it will run in O(n log n) time (I don't know about the constants... try it and see if it's fast enough; should take about as much time as figuring out how to interface with some existing library :p). The linked fft-cpp code shows there's not much more to it than that (though I'd prefer working over a finite field rather than complex numbers). – ShreevatsaR Jul 31 '10 at 03:31
  • @ShreevastsaR: Attribution is not acceptable because the goal is to contribute it to the standard library, which has a strict policy against requiring attribution for works distributed in binary-only form. For a standard library, this requirement seems fairly reasonable. – dsimcha Jul 31 '10 at 05:59
  • @ShreevastaR: Also, as far as writing my own from scratch, I prefer not to only because getting non-power of two sizes to work efficiently seems rather difficult. I've written my own FFT from scratch for real-only power of 2 size inputs, though, and you're right, it's not that hard. – dsimcha Jul 31 '10 at 06:10

1 Answers1

4

Kiss FFT, by Mark Borgerding, meets your requirements except that it's BSD licensed. It may be worth your while to contact him and see if he's interested in giving you an exception for the license. There's a bit of pre-processor abuse but only to handle fixed- and floating-point data types.

mtrw
  • 34,200
  • 7
  • 63
  • 71