{{ message }}

Instantly share code, notes, and snippets.

# lukicdarkoo/FFT.c

Last active Sep 23, 2021
Basic implementation of Cooley-Tukey FFT algorithm in C++
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #include "FFT.h" void fft(int *x_in, std::complex *x_out, int N) { // Make copy of array and apply window for (int i = 0; i < N; i++) { x_out[i] = std::complex(x_in[i], 0); x_out[i] *= 1; // Window } // Start recursion fft_rec(x_out, N); } void fft_rec(std::complex *x, int N) { // Check if it is splitted enough if (N <= 1) { return; } // Split even and odd std::complex odd[N/2]; std::complex 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 t = exp(std::complex(0, -2 * M_PI * k / N)) * odd[k]; x[k] = even[k] + t; x[N / 2 + k] = even[k] - t; } }
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* --------------------------------------------------------------------------- ** Basic implementation of Cooley-Tukey FFT algorithm in C++ ** ** Author: Darko Lukic ** -------------------------------------------------------------------------*/ #ifndef FFT_h #define FFT_h #include #include extern void fft(int *x_in, std::complex *x_out, int N); void fft_rec(std::complex *x, int N); #endif

### russellu commented May 17, 2020

 amazing

### Metabog commented Nov 28, 2020

 This is a great implementation. No weird data types and building stuff with cmake, just basic, working code.

### funham commented Mar 10, 2021

 This is pretty good, but is it actually Cooley-Tukey FFT algorithm? I am looking for a non-recursive FFT algotithm...
to join this conversation on GitHub. Already have an account? Sign in to comment