c++ - FFT算法中的一个错误

Question

我的 friend 们，我现在正在编写 FFT 算法，我有以下程序:

#include<iostream>
#include<vector>
#include<complex>
#include<cmath>
#define _USE_MATH_DEFINES
#include<math.h>
#include<stdlib.h>

using namespace std;

const complex<double> I(0,1);
const int pi = M_PI;

//This function will check if a number is a power of certain number 
bool checkpower(float base,float num){
    float a = ceil(log(num)/log(base))-floor(log(num)/log(base));
    if (a==0){
        return 1;
    }
    else{
    return 0;
    }
}


//Fast Fourier Transform for DFT
vector<complex<double>> FFT_DFT(vector<complex<double>> samples){
    int N = samples.size();
    cout << N << endl;
    if(!checkpower(2,N)){
        cout << "Please make sure the sample size is of 2^n!" << endl;
        exit (EXIT_FAILURE);
    }
    else{
        vector<complex<double>> F(N);
        if(N==1){
            F.push_back(samples[0]);
        }
        else{
            int M = N/2;
            cout << M << endl;
            vector<complex<double>> O; //vector to store the odd elements
            vector<complex<double>> E; //vector to store the even elements
            //Reoder the samples
            for(int l=0;l<M;l++){
                E.push_back(samples[2*l]);
                O.push_back(samples[2*l+1]);
            }
            vector<complex<double>> ODFT;
            cout << "Start recursive for odd" << endl;
            ODFT = FFT_DFT(O);
            vector<complex<double>> EDFT;
            cout << "Start recursive for even" << endl;
            EDFT = FFT_DFT(E);
            for(int k=0;k<M;k++){
                cout << real(EDFT[k]) << " + "<< imag(EDFT[k]) << "I" << endl;
                cout << real(ODFT[k]) << " + "<< imag(ODFT[k]) << "I" << endl;
                F[k] = EDFT[k]+exp(-2.0*pi*k*I/(double)N)*ODFT[k];
                F[k+M] = EDFT[k]-exp(-2.0*pi*k*I/(double)N)*ODFT[k]; 
                cout << real(F[k]) << " + "<< imag(F[k]) << "I" << endl;
                cout << real(F[k+M]) << " + "<< imag(F[k+M]) << "I" << endl;
            }
        }
        return F;
    }
}


int main(){
    vector<complex<double>> samples;
    samples.push_back(8.0);
    samples.push_back(4.0);
    samples.push_back(8.0);
    samples.push_back(0.0);

    vector<complex<double>> dft = FFT_DFT(samples);
    vector<complex<double>>::iterator item;

    for(item=dft.begin();item!=dft.end();item++){
        cout << real(*item) << " + "<< imag(*item) << "I" << endl;
    }


    return 0;
}

我使用 visual studio 2010 professional 作为编译器。我不知道我的递归算法有什么问题，所以我在 VS 中使用了 Debug模式，并逐行检查了程序，但它似乎总是给我所有值 0。我用普通的 FFT 算法对其进行了测试，它运行良好。那么，任何人都可以帮我看看我的程序吗？我已经调试了大约 4 个小时，但仍然找不到错误。也许，我做了一些非常愚蠢的事情而我没有注意到。

(请注意，在 FFT 函数中，为了看看到底发生了什么，我还添加了很多 cout 行)

谢谢你帮助我!

Answer 1

替换

F.push_back(samples[0]);

向 F 添加一个元素 - 它已经有一个元素，零 -

F[0] = samples[0];

您将以第一个元素为零、第二个元素为样本的 vector 结束递归。
由于您稍后仅使用第一个元素，因此一切都变为零。