2 ms·
For those who just want to play around with Fourier transforms, it is worth noting that computers are fast enough nowadays that you can often get away with a sl
by tzs 9y ago
For those who just want to play around with Fourier transforms, it is worth noting that computers are fast enough nowadays that you can often get away with a slow Fourier transform instead of a fast Fourier transform. The former is O(N^2) as opposed to O(N log N), but is also much easier to understand. To wit, in C, here is a function that takes a pointer to an input array of complex numbers, and output array of complex numbers, and a count of how many numbers are in the input, and does a discrete slow Fourier transform from the input array to the output array:
#include <math.h>
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;
}
}
}
This is a pretty direct implementation of the definition of a discrete Fourier transform as given in equation 1 from the Wikipedia article on DFT [1].
On my iMac (3.4 GHz Intel Core i5), compiled with "cc -Ofast", here are timings:
size time/FT FTs/sec
---- --------- -------
128 0.24 ms 4167
256 0.93 ms 1074
512 3.8 ms 263
1024 15.5 ms 65
2048 65.6 ms 15
4096 243 ms 4
That would plenty fast for many interesting learning projects, like a real time guitar tuner for example.
[1] https://en.wikipedia.org/w/index.php?title=Discrete_Fourier_transform&oldid=809829098 https://en.wikipedia.org/w/index.php?title=Discrete_Fourier_...