Code:

<<complex number datatype>>=
typedef struct complex_t {
double re;
double im;
} complex;
<<complex number prototypes>>=
complex complex_from_polar(double r, double theta_radians);
double complex_magnitude(complex c);
complex complex_add(complex left, complex right);
complex complex_sub(complex left, complex right);
complex complex_mult(complex left, complex right);
<<complex number function definitions>>=
complex complex_from_polar(double r, double theta_radians) {
complex result;
result.re = r * cos(theta_radians);
result.im = r * sin(theta_radians);
return result;
}
double complex_magnitude(complex c) {
return sqrt(c.re*c.re + c.im*c.im);
}
complex complex_add(complex left, complex right) {
complex result;
result.re = left.re + right.re;
result.im = left.im + right.im;
return result;
}
complex complex_sub(complex left, complex right) {
complex result;
result.re = left.re - right.re;
result.im = left.im - right.im;
return result;
}
complex complex_mult(complex left, complex right) {
complex result;
result.re = left.re*right.re - left.im*right.im;
result.im = left.re*right.im + left.im*right.re;
return result;
}

That's pretty easy I find, this should be a header that defines complex type and operation (though here complex are defined with double for both real and img part, but I think I can convert all this stuff for float).Here it is the code for FFT operation:
Code:

complex* FFT_simple(complex* x, int N /* must be a power of 2 */) {
complex* X = (complex*) malloc(sizeof(struct complex_t) * N);
complex * d, * e, * D, * E;
int k;
if (N == 1) {
X[0] = x[0];
return X;
}
e = (complex*) malloc(sizeof(struct complex_t) * N/2);
d = (complex*) malloc(sizeof(struct complex_t) * N/2);
for(k = 0; k < N/2; k++) {
e[k] = x[2*k];
d[k] = x[2*k + 1];
}
E = FFT_simple(e, N/2);
D = FFT_simple(d, N/2);
free(e);
free(d);
for(k = 0; k < N/2; k++) {
/* Multiply entries of D by the twiddle factors e^(-2*pi*i/N * k) */
D[k] = complex_mult(complex_from_polar(1, -2.0*PI*k/N), D[k]);
}
for(k = 0; k < N/2; k++) {
X[k] = complex_add(E[k], D[k]);
X[k + N/2] = complex_sub(E[k], D[k]);
}
free(D);
free(E);
return X;
}

Until now I think code is pretty linear, but I have some question.The function receives as parameter my vector to FFT, then a int value n, that's said to be a power of 2. What is N? The size of the vector? Or the sampling frequency I want to use (usually it should be twice the number of the samples of the vector).This implementation is said to be a little bit rude, and it can be better (it says uses 3x necessary memory for allocation, and it has a performance degrade for large input, like my vectors that are 1024 elements long).The guide proposes a new implementation:

Code:

void FFT_calculate(complex* x, int N /* must be a power of 2 */, int skip,
complex* X, complex* D, complex* twiddles) {
complex * E = D + N/2;
int k;
if (N == 1) {
X[0] = x[0];
return;
}
/* for now we can use X as a scratch buffer */
FFT_calculate(x, N/2, skip*2, E, X, twiddles);
FFT_calculate(x + skip, N/2, skip*2, D, X, twiddles);
for(k = 0; k < N/2; k++) {
/* Multiply entries of D by the twiddle factors e^(-2*pi*i/N * k) */
D[k] = complex_mult(twiddles[k*skip], D[k]);
}
for(k = 0; k < N/2; k++) {
X[k] = complex_add(E[k], D[k]);
X[k + N/2] = complex_sub(E[k], D[k]);
}
}
complex* FFT_get_twiddle_factors(int N) {
complex* twiddles = (complex*) malloc(sizeof(struct complex_t) * N/2);
int k;
for (k = 0; k != N/2; ++k) {
twiddles[k] = complex_from_polar(1.0, -2.0*PI*k/N);
}
return twiddles;
}
complex* FFT_simple(complex* x, int N /* must be a power of 2 */) {
complex* out = (complex*) malloc(sizeof(struct complex_t) * N);
complex* scratch = (complex*) malloc(sizeof(struct complex_t) * N);
complex* twiddles = FFT_get_twiddle_factors(N);
FFT_calculate(x, N, 1, out, scratch, twiddles);
free(twiddles);
free(scratch);
return out;
}

It's said to be the best implementation of the alghoritm, but it gets lot of parameters I can't really understand.What are twiddles? What is the twiddle array?What is int skip?What are X and D array?For now these are my question, they really can't let me understand the code...For now I could use the first implementation too, if the best one becomes to difficult to understand, but I'm in need to know at least what parameter n means, and if someone's a little expert about this kind of operation, if he knows more efficient or easier ways to implement FFT.Thank you all for your attention and help, I'm giving my best effort in understanding this code. I usually try to implement software by myself, but in this case it's obvious it's better to understand famous and tested software created by "autorithies", I think...