http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html
General Purpose FFT (Fast Fourier/Cosine/Sine Transform) Package
1-dim DFT / DCT / DST

*This is a package to calculate Discrete Fourier/Cosine/Sine Transforms of
1-dimensional sequences of length 2^N. This package contains C and Fortran FFT codes.

*2-dim/3-dim DFT / DCT / DST
2,3-dimensional sequences of length 2^N.

*Benchmark
http://www.kurims.kyoto-u.ac.jp/~ooura/fftbmk.html