Fast Fourier transform: Difference between revisions
Content added Content deleted
m (→{{header|Tcl}}: Make it clearer what is produced) |
|||
| Line 2: | Line 2: | ||
The purpose of this task is to calculate the FFT (Fast Fourier Transform) of an input sequence. The most general case allows for complex numbers at the input and results in a sequence of equal length, again of complex numbers. If you need to restrict yourself to real numbers the output should be the magnitude (i.e. sqrt(re²+im²)) of the complex result. The classic version is the recursive Cooley–Tukey FFT. [http://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm Wikipedia] has pseudocode for that. Further optimizations are possible but not required. |
The purpose of this task is to calculate the FFT (Fast Fourier Transform) of an input sequence. The most general case allows for complex numbers at the input and results in a sequence of equal length, again of complex numbers. If you need to restrict yourself to real numbers the output should be the magnitude (i.e. sqrt(re²+im²)) of the complex result. The classic version is the recursive Cooley–Tukey FFT. [http://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm Wikipedia] has pseudocode for that. Further optimizations are possible but not required. |
||
<lang d>import std.stdio, std.math, std.algorithm, std.range; |
|||
| ⚫ | |||
auto fft(creal[] x) { |
|||
int N = x.length; |
|||
if (N <= 1) return x; |
|||
auto ev = fft(array(stride(x, 2))); |
|||
auto od = fft(array(stride(x[1 .. $], 2))); |
|||
//auto l = map!((k){return ev[k]+expi(-2*PI*k/N)*od[k];})(iota(N/2)); |
|||
//auto r = map!((k){return ev[k]-expi(-2*PI*k/N)*od[k];})(iota(N/2)); |
|||
creal[] l, r; |
|||
foreach (k; 0 .. N/2) { |
|||
l ~= ev[k] + expi(-2 * PI * k / N) * od[k]; |
|||
r ~= ev[k] - expi(-2 * PI * k / N) * od[k]; |
|||
} |
|||
return array(chain(l, r)); |
|||
} |
|||
void main() { |
|||
writeln(fft([1.0L+0i, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0])); |
|||
}</lang> |
|||
Output:<pre>[4+0i, 1+-2.41421i, 0+0i, 1+-0.414214i, 0+0i, 1+0.414214i, 0+0i, 1+2.41421i]</pre> |
|||
| ⚫ | |||
Based on [[j:Essays/FFT]], with some simplifications, sacrificing accuracy, optimizations and convenience not visible here, for clarity: |
Based on [[j:Essays/FFT]], with some simplifications, sacrificing accuracy, optimizations and convenience not visible here, for clarity: |
||