Skip to content

Instantly share code, notes, and snippets.

@lukicdarkoo
Last active Sep 23, 2021
Embed
What would you like to do?
Basic implementation of Cooley-Tukey FFT algorithm in C++
#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;
}
}
/* ---------------------------------------------------------------------------
** Basic implementation of Cooley-Tukey FFT algorithm in C++
**
** Author: Darko Lukic <lukicdarkoo@gmail.com>
** -------------------------------------------------------------------------*/
#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
@russellu

This comment has been minimized.

Copy link

@russellu russellu commented May 17, 2020

amazing

@Metabog

This comment has been minimized.

Copy link

@Metabog Metabog commented Nov 28, 2020

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

@funham

This comment has been minimized.

Copy link

@funham 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...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment