3 ms·
If you don't need it in real time and don't have a whole lot of points, you can do discrete Fourier transforms in even less code by just doing FT instead of FFT
by tzs 6y ago
If you don't need it in real time and don't have a whole lot of points, you can do discrete Fourier transforms in even less code by just doing FT instead of FFT. Modern computers are fast enough that the most straightforward O(n^2) algorithm that is immediately obvious from the definition of the discrete Fourier transform given in Wikipedia will often be fast enough. E.g., something like this in C:
typedef struct {
double r;
double i;
} complex;
void fourier(complex * x, complex * y, int np)
{
int n, k;
for (k = 0; k < np; ++k)
{
y[k].r = y[k].i = 0;
for (n = 0; n < np; ++n)
{
double c = cos(2*M_PI*k*n/np);
double s = sin(2*M_PI*k*n/np);
y[k].r += x[n].r * c + x[n].i * s;
y[k].i += -x[n].r * s + x[n].i * c;
}
}
}
20 years ago, on a middle of the road desktop, that was fast enough that I was able to do an almost real time guitar tuner with it.