FFTW3

FFTWは，驚く程速い（らしい）FFTのライブラリ．各CPUに最適化されている．
コンパイル時ではなく実行時に最適なアルゴリズムが選択されるらしい．

FFTW3の簡単なサンプル．コンパイルできるか確認用に．

#include <stdio.h>
#include <fftw3.h>
#include <math.h>

#define N 65536

int main(void)
{
  fftw_complex *in, *out;
  fftw_plan p;
  unsigned long t;

  in  = fftw_malloc(sizeof(fftw_complex) * N);
  out = fftw_malloc(sizeof(fftw_complex) * N);

  for(t=0;t<N;t++){
        in[t][0]=sin((double)t*(2.0*M_PI*100.0/(double)N));
        in[t][1]=0.0;
  }

  p = fftw_plan_dft_1d(N, in, out, FFTW_FORWARD, FFTW_ESTIMATE);

  fftw_execute(p);                                   // fft の実行

  for(t=0;t<N;t++){
        printf("%d\t",t);
        printf("%lf\t",sqrt(out[t][0]*out[t][0]+out[t][1]*out[t][1]));
        printf("%lf\t",out[t][0]);
        printf("%lf\n",out[t][1]);
  }

  fftw_destroy_plan(p);                                   // plan の破棄
  fftw_free(in); fftw_free(out);
}

コンパイルは

gcc -o testfftw testfftw.c -lfftw3 -lm