complex.c

struct ComplexNumber{
    float Real;
    float Im;
};


struct ComplexNumber init_complex_number(float Real, float Im){
    struct ComplexNumber out;
    out.Real = Real;
    out.Im = Im;
    return out;
}


void print_complex_number(struct ComplexNumber e){
    printf("%f + i %f \n", e.Real, e.Im);
}


struct ComplexNumber complex_exp(float theta){
    return init_complex_number(cos(theta), sin(theta));
};


struct ComplexNumber complex_add(struct ComplexNumber x, struct ComplexNumber y){
    return init_complex_number(x.Real+y.Real, x.Im+y.Im);
};


struct ComplexNumber complex_subtract(struct ComplexNumber x, struct ComplexNumber y){
    return init_complex_number(x.Real-y.Real, x.Im-y.Im);
};


struct ComplexNumber complex_mult(struct ComplexNumber x, struct ComplexNumber y){
    float re = (x.Real * y.Real) - (x.Im * y.Im);
    float im = (x.Im * y.Real) + (x.Real * y.Im);
    return init_complex_number(re, im);
}

fft.c

#include<stdio.h>
#include<math.h>
#include"complex.c"


struct ComplexNumber *fft(struct ComplexNumber sig[], int N, int stride){
    if(N==1)
        return sig;
    else{
        struct ComplexNumber sig_1[N/2], sig_2[N/2], temp;
        struct ComplexNumber *fft_1, *fft_2, *out;

        for (int i=0; i<N/2; i++){
            sig_1[i] = sig[i];
            sig_2[i] = sig[i+N/2];
        }

        fft_1 = fft(sig_1, N/2, 2*stride);
        fft_2 = fft(sig_2, N/2, 2*stride);

        for (int i=0; i<N/2; i++){
            sig[i] = fft_1[i];
            sig[i+N/2] = fft_2[i];
        }

        for (int k=0; k<N/2; k++){
            temp = sig[k];
            struct ComplexNumber weight = complex_mult(complex_exp(-2*M_PI*k/N), sig[k+N/2]);
            sig[k] = complex_add(temp, weight);
            sig[k+N/2] = complex_subtract(temp, weight);
        }
        return sig;
    }
}


int main(){
    int N=4;
    float raw_signal[] = {1, 0, 1, 0};
    struct ComplexNumber sig[N], *sig_fft;

    for (int i=0; i<N; i++)
        sig[i] = init_complex_number(raw_signal[i], 0);

    sig_fft = fft(sig, N, 1);

    for (int i=0; i<N; i++)
        print_complex_number(sig_fft[i]);

    return 0;
}