C++ FFT實現（架構x86_64的未定義符號）

Question

我正試圖在C++中實現FFT。但是我得到這個錯誤：

Undefined symbols for architecture x86_64: 
    "Complex::fft(std::vector<Complex*, std::allocator<Complex*> >*)", referenced from: 
     _main in ccMdeaRo.o 
ld: symbol(s) not found for architecture x86_64 
collect2: ld returned 1 exit status 

這裏是我的代碼：

// Complex.h ----------------------------------------------------------------- 
#include <cmath> 
#include <string> 
#include <sstream> 
#include <vector> 

using namespace std; 
class Complex { 

float _re,_im; 

public: 
    static Complex ZERO; 
    static Complex ONE; 
    static const float TOLERANCE = 5E-6f; 

    Complex(float re, float im); 
    // Polar(float r, float theta); 
    // ~Complex(); 

    float angle(); 
    float magnitude(); 
    bool equals(Complex* arg); 
    Complex* clone(); 
    static vector<Complex*>* fft(vector<Complex*>* a); 
    // static Complex** fft(Complex** a, long n); 
    static Complex* omega(long n); 
    static Complex* polar(float r, float theta); 
    float re(); 
    float im(); 
    Complex* minus(Complex* that); 
    Complex* plus(Complex* that); 
    Complex* times(Complex* that); 
    string toString(); 

}; 

// Complex.cpp ----------------------------------------------------------------- 
#include "Complex.h" 

Complex::Complex(float re, float im) { 
this->_re = re; 
this->_im = im; 
} 


float Complex::angle(){ 
return atan2(_im,_re); 
} 

float Complex::magnitude() { 
return sqrt(this->_re * _re + this->_im * _im); 
} 

Complex* Complex::omega(long n) { 
    Complex* cplx = polar(1.0, 2*(M_PI)/n); 
return cplx; 
} 


vector<Complex*>* fft(vector<Complex*>* a) { 
long n = a->size(); 
if (n == 1) { 
    return a; 
} 

Complex* w_n = Complex::omega(n); 
Complex* w = new Complex(1,0); 

long half_n = n/2; 

vector<Complex*>* aEvens = new vector<Complex*>(half_n); 
vector<Complex*>* aOdds = new vector<Complex*>(half_n); 

for (long i = 0; i < n; i++) { 
    if (i % 2 == 0) { 
     aEvens->push_back(a->at(i)); 
    } 
    else { 
     aOdds->push_back(a->at(i)); 
    } 
} 

vector<Complex*>* yEvens = fft(aEvens); 
vector<Complex*>* yOdds = fft(aOdds); 
vector<Complex*>* y = new vector<Complex*>(n); 

y->resize(n, 0); 

for (long k = 0; k < n/2; k++) { 
    Complex* prod = (yOdds->at(k))->times(w); 
    y->at(k) = yEvens->at(k)->plus(prod); 
    y->at(k+half_n) = yEvens->at(k + half_n)->minus(prod); 
    w = w->times(w_n); 
} 

delete w; 
delete w_n; 

return y; 
} 

Complex* Complex::polar (float r, float theta) { 
Complex* cplx = new Complex(r*cos(theta),r*sin(theta)); 
return cplx; 
} 

bool Complex::equals(Complex* arg) { 
double d_re = abs(this->_re - arg->_re); 
double d_im = abs(this->_im - arg->_im); 

return (d_re < TOLERANCE && d_im < TOLERANCE); 
} 

Complex* Complex::clone() { 
Complex* theClone = new Complex(this->_re,this->_im); 
return theClone; 
} 

float Complex::re() { 
return this->_re; 
} 

float Complex::im() { 
return _im; 
} 

Complex* Complex::minus(Complex* arg) { 
float diff_re = this->_re - arg->_re; 
float diff_im = this->_im - arg->_im; 
Complex* diff = new Complex(diff_re, diff_im); 
return diff; 
} 

Complex* Complex::plus(Complex* arg) { 
float sum_re = this->_re + arg->_re; 
float sum_im = this->_im + arg->_im; 
Complex* sum = new Complex(sum_re, sum_im); 
return sum; 
} 

Complex* Complex::times(Complex* arg) { 
float magn = this->magnitude() * arg->magnitude(); 
float angl = this->angle() + arg->angle(); 
Complex* prod = polar(magn, angl); 
return prod; 
} 

string Complex::toString() { 
ostringstream s; 
s << this->_re << " + " << this->_im << "i"; 
return s.str(); 
} 



// main ----------------------------------------------------------------- 

#include "complex.h" 
#include <iostream> 

int main() { 
    Complex* a = new Complex(1,0); 
    Complex* b = new Complex(0,1); 
    Complex* c = new Complex(5,5); 
    Complex* d = new Complex(6,2); 
    Complex* e = a -> clone(); 
    Complex* f = a->plus(b); 
    Complex* g = a->minus(b); 
    Complex* h = c->times(d); 
    Complex* j = Complex::omega(4); 
    Complex* k = Complex::polar(1, 2*(M_PI)); 
    cout << "a:\t" << a->toString() << endl; 
    cout << "b:\t" << b->toString() << endl; 
    cout << "a->re():\t" << a->re() << endl; 
    cout << "a->im():\t" << a->im() << endl; 
    cout << "a plus b:\t" << f->toString() << endl; 
    cout << "a minus b:\t" << g->toString() << endl; 
    cout << "c times d:\t" << h->toString() << endl; 
    cout << "omega(4):\t" << j ->toString() << endl; 
    cout << "j->equals(b):\t" << j->equals(b) << endl; 
    cout << "j->equals(c):\t" << j->equals(c) << endl; 
    cout << "polar(1, 2PI):\t" << k->toString() << endl; 
    cout << "k->equals(a):\t" << k->equals(a) << endl;  
    cout << "k->equals(b):\t" << k->equals(b) << endl; 
    cout << "a->clone():\t" << e->toString() << endl; 

    Complex* one = new Complex(1,0); 
    Complex* two = new Complex(2,0); 
    Complex* three = new Complex(3,0); 
    Complex* four = new Complex(4,0); 

    vector<Complex*>* cplxVec = new vector<Complex *>; 
    cplxVec->push_back(one); 
    cplxVec->push_back(two); 
    cplxVec->push_back(three); 
    cplxVec->push_back(four); 

    cout << "\nPrinting out vector:\n" << endl; 

    for (unsigned int i = 0; i < cplxVec->size(); i++) { 
     cout << cplxVec->at(i) -> toString() << endl; 
    } 

    cout << endl; 


    Complex::fft(cplxVec); 


    return 0; 
} 

Answer 1

當你實現fft你忘了Complex::：

vector<Complex*>* fft(vector<Complex*>* a) { 

應該是：

vector<Complex*>* Complex::fft(vector<Complex*>* a) { 

fft有一個問題，它進入一個無限循環在這裏，當它自稱：

vector<Complex*>* yEvens = fft(aEvens); 

您減半不能讓他們到的1大小。