Skip to content

Instantly share code, notes, and snippets.

@lukicdarkoo

lukicdarkoo/FFT.c

Last active August 23, 2025 04:45
Show Gist options
  • Save lukicdarkoo/3f0d056e9244784f8b4a to your computer and use it in GitHub Desktop.
Save lukicdarkoo/3f0d056e9244784f8b4a to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. lukicdarkoo revised this gist Dec 19, 2015. 1 changed file with 11 additions and 0 deletions.
    11 changes: 11 additions & 0 deletions FFT.h
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,18 @@
    /* ---------------------------------------------------------------------------
    ** Basic implementation of Cooley-Tukey FFT algorithm in C++
    **
    ** Author: Darko Lukic <[email protected]>
    ** -------------------------------------------------------------------------*/

    #ifndef FFT_h
    #define FFT_h

    #include <cmath>
    #include <complex>

    extern void fft(int *x_in,
    std::complex<double> *x_out,
    int N);
    void fft_rec(std::complex<double> *x, int N);

    #endif
  2. lukicdarkoo created this gist Dec 19, 2015.
    42 changes: 42 additions & 0 deletions FFT.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,42 @@
    #include "FFT.h"

    void fft(int *x_in,
    std::complex<double> *x_out,
    int N) {

    // Make copy of array and apply window
    for (int i = 0; i < N; i++) {
    x_out[i] = std::complex<double>(x_in[i], 0);
    x_out[i] *= 1; // Window
    }

    // Start recursion
    fft_rec(x_out, N);
    }

    void fft_rec(std::complex<double> *x, int N) {
    // Check if it is splitted enough
    if (N <= 1) {
    return;
    }

    // Split even and odd
    std::complex<double> odd[N/2];
    std::complex<double> even[N/2];
    for (int i = 0; i < N / 2; i++) {
    even[i] = x[i*2];
    odd[i] = x[i*2+1];
    }

    // Split on tasks
    fft_rec(even, N/2);
    fft_rec(odd, N/2);


    // Calculate DFT
    for (int k = 0; k < N / 2; k++) {
    std::complex<double> t = exp(std::complex<double>(0, -2 * M_PI * k / N)) * odd[k];
    x[k] = even[k] + t;
    x[N / 2 + k] = even[k] - t;
    }
    }
    7 changes: 7 additions & 0 deletions FFT.h
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,7 @@
    #include <cmath>
    #include <complex>

    extern void fft(int *x_in,
    std::complex<double> *x_out,
    int N);
    void fft_rec(std::complex<double> *x, int N);