2 ms·

For anyone interested in a simple implementation of FFT, I found this neat little example which was very grokkable if you speak Java: https://introcs.cs.prince

by gleenn 9y ago

For anyone interested in a simple implementation of FFT, I found this neat little example which was very grokkable if you speak Java: https://introcs.cs.princeton.edu/java/97data/FFT.java.html https://introcs.cs.princeton.edu/java/97data/FFT.java.html

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_...

by gleenn 9y ago

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_...