快速傅里叶变换:第一个元素是正确的，但其余元素不正确

Question

我正在实现FFT，我的解决方案可以始终如一地解决转换的第一个元素，但不能完成其余的工作。

这是代码：

vector<complex<double>> FFT(vector<complex<double>> a, complex<double> w)
{
    if (a.size() == 1) {
        return a;
    }
    vector<complex<double>> even;
    vector<complex<double>> odd;
    for (int i = 0; i < a.size(); i ++) {
        if (i % 2 == 0) {
            even.push_back(a[i]);
        }
        else {
             odd.push_back(a[i]);
        }
    }
    vector<complex<double>> FFTeven = FFT(even, nthRoot(a.size() / 2));
    vector<complex<double>> FFTodd = FFT(odd, nthRoot(a.size() / 2));
    vector<complex<double>> ret;
    for (int i = 0; i < a.size(); i++) {
    ret.push_back(0);
    }
    for (int i = 0; i <= (a.size() / 2) - 1; i++) {
        ret[i] = FFTeven[i] + pow(w, i) * FFTodd[i];
        ret[i + a.size() / 2] = FFTeven[i] - pow(w, i) * FFTodd[i];
    }
    return ret;
}

主代码：

int n = 4;
vector <complex<double>> a;
vector<complex<double>> b;
for (int i = 1; i < 9; i++) {
    if (i < 5) {
        a.push_back((complex<double>) i);
    }
    else {
        b.push_back((complex<double>) i);
    }
}
for (int i = 0; i < n; i++) {
    a.push_back(0);
    b.push_back(0);
}
complex<double> w = nthRoot(a.size());
a = FFT(a, w);
b = FFT(b, w);
for (int i = 0; i < a.size() - 1; i++) {
    cout << a[i].real() << ", ";
}
cout << a.back().real() << ">n";
for (int i = 0; i < b.size() - 1; i++) {
    cout << b[i].real() << ", ";
}
cout << b.back().real() << ">n";

第 n 个根：

complex<double> nthRoot(int n)
{
    return (cos(2 * M_PI / n) + i * sin(2 * M_PI / n));
}

我在全球范围内声明：

const complex<double> i = (0.0, 1.0);

示例输入：

a = <5， 6， 7， 8， 0， 0， 0， 0>

示例输出：

ret = <26， 31.799， -6， -7.65685， -2， -7.79899， 2， 3.65685>

预期输出：

ret = <26， 3.5858， -2， 6.4142，

-2， 6.4142， -2， 3.5858>

该FFT用于查找卷积，因此在输入向量末尾填充零。任何帮助都会得到赞赏。

Answer 1

好吧，

我通过运行您的代码获得了您预期的输出。唯一的区别是当我pushback 0 时，我必须使用 push_back(complex<double>(0)) .我认为这并不重要。

您是否搞砸了预期结果和示例结果？

如果有人对这个FFT示例感兴趣，我将"复制-粘贴-运行"版本放在下面：

#include <stdio.h>
#include <iostream>
#include <vector>
#include <complex>
using namespace std;
complex<double> nthRoot(int n)
{
    return complex<double>(cos(2 * M_PI / n), sin(2 * M_PI / n));
}
vector<complex<double> > FFT(vector<complex<double> > a, complex<double> w)
{
    if (a.size() == 1) {
        return a;
    }
    vector<complex<double> > even;
    vector<complex<double> > odd;
    for (int i = 0; i < a.size(); i ++) {
        if (i % 2 == 0) {
            even.push_back(a[i]);
        }
        else {
             odd.push_back(a[i]);
        }
    }
    vector<complex<double> > FFTeven = FFT(even, nthRoot(a.size() / 2));
    vector<complex<double> > FFTodd = FFT(odd, nthRoot(a.size() / 2));
    vector<complex<double> > ret;
    for (size_t i = 0; i < a.size(); i++) {
        ret.push_back(complex<double>(0));
    }
    for (size_t i = 0; i <= (a.size() / 2) - 1; i++) {
        ret[i] = FFTeven[i] + pow(w, i) * FFTodd[i];
        ret[i + a.size() / 2] = FFTeven[i] - pow(w, i) * FFTodd[i];
    }
    return ret;
}
int main(void) {
  int n = 4;
  vector<complex<double> > a;
  vector<complex<double> > b;
  for (int i = 1; i < 9; i++) {
      if (i < 5) {
          a.push_back((complex<double>) i);
      }
      else {
          b.push_back((complex<double>) i);
      }
  }
  for (int i = 0; i < n; i++) {
      a.push_back(complex<double>(0));
      b.push_back(complex<double>(0));
  }
  complex<double> w = nthRoot(a.size());
  a = FFT(a, w);
  b = FFT(b, w);
  for (int i = 0; i < a.size() - 1; i++) {
      cout << a[i].real() << ", ";
  }
  cout << a.back().real() << ">n";
  for (int i = 0; i < b.size() - 1; i++) {
      cout << b[i].real() << ", ";
  }
  cout << b.back().real() << ">n";
}

输出为

10， -0.414214， -2， 2.41421， -2， 2.41421，

-2， -0.414214>

26， 3.58579， -2， 6.41421， -2，

6.41421， -2， 3.58579>