寻找关于FFT模板的帮助

Question

我目前正在研究需要FFT进行卷积的问题，但是当我从我的存档中引入FFT模板时，我发现输出存在问题。

例如：

输入：（0,0）（0,0）（4166667，0）（1，0）

正确的输出：（4166668，0）（-4166667， 1）（4166666，0）（-4166667，-1）

模板输出：（4166668，0）（-4166667，-1）（4166666，0）（-4166667，）

代码：

#define MAXN 
#define ld long double 
#define op operator 

struct base { 
    typedef ld T; T re, im; 
    base() :re(0), im(0) {} 
    base(T re) :re(re), im(0) {} 
    base(T re, T im) :re(re), im(im) {} 
    base op + (const base& o) const { return base(re + o.re, im + o.im); } 
    base op - (const base& o) const { return base(re - o.re, im - o.im); } 
    base op * (const base& o) const { return base(re * o.re - im * o.im, re * o.im + im * o.re); } 
    base op * (ld k) const { return base(re * k, im * k); } 
    base conj() const { return base(re, -im); } 
}; 

base w[MAXN]; //omega lookup table 
int rev[MAXN]; //reverse lookup table 

void build_rev(int k) { 
    static int rk = -1; 
    if(k == rk)return ; rk = k; 
    for(int i = 1; i < (1<<k); i++) { 
     int j = rev[i-1], t = k-1; 
     while(t >= 0 && ((j>>t)&1)) { j ^= 1 << t; --t; } 
     if(t >= 0) { j ^= 1 << t; --t; } 
     rev[i] = j; 
    } 
} 

void fft(base *a, int k) { 
    build_rev(k); int n = 1 << k; 
    for(int i = 0; i < n; i++) if(rev[i] > i) swap(a[i], a[rev[i]]); 
    for(int l = 2, lll = 1; l <= n; l += l, lll += lll) { 
     if(w[lll].re == 0 && w[lll].im == 0) { 
      ld angle = PI/lll; 
      base ww(cosl(angle), sinl(angle)); 
      if(lll > 1) for(int j = 0; j < lll; ++j) { 
       if(j & 1) w[lll + j] = w[(lll+j)/2] * ww; 
       else w[lll + j] = w[(lll+j)/2]; 
      } else w[lll] = base(1, 0); 
     } 
     for(int i = 0; i < n; i += l) 
     for(int j = 0; j < lll; j++){ 
      base v = a[i + j], u = a[i + j + lll] * w[lll + j]; 
      a[i + j] = v + u; a[i + j + lll] = v - u; 
      } 
    } 
} 

//ideone compiled example: http://ideone.com/8PTjW5 

我试图检查位反向统一表的根但我没有发现在这两个部分的任何问题。我也检查了一些在线资料来验证步骤，但没有什么奇怪的东西给我看。

会有人介意帮我找出这个模板有什么问题吗？

在此先感谢。

编辑：我决定在最后依靠另一个模板，感谢所有人的回复。

Answer 1

它看起来像你的权重有错误的符号（这意味着你可能做了反FFT而不是正向FFT - 记住正向变换the weights are exp(-j * theta)）。尝试改变：

base ww(cosl(angle), sinl(angle)); 

到：

base ww(cosl(angle), -sinl(angle)); 

这seems to give the correct results为您简单的测试案例。我还没有尝试过任何更苛刻的测试。

巧合的是另一位用户最近made exactly the same mistake in a MATLAB implementation。我猜-标志很容易错过。

还要注意，你的代码效率很低 - 你可能要考虑使用一个简单的，经过验证的FFT库，如KissFFT。