2015-02-20 00:35:01 -05:00
|
|
|
|
{{omit from|GUISS}}
|
2016-12-05 22:15:40 +01:00
|
|
|
|
|
|
|
|
|
|
;Task:
|
|
|
|
|
|
Calculate the FFT (<u>F</u>ast <u>F</u>ourier <u>T</u>ransform) of an input sequence.
|
|
|
|
|
|
|
2015-02-20 00:35:01 -05:00
|
|
|
|
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.
|
|
|
|
|
|
|
2016-12-05 22:15:40 +01:00
|
|
|
|
The classic version is the recursive Cooley–Tukey FFT. [http://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm Wikipedia] has pseudo-code for that.
|
2015-02-20 00:35:01 -05:00
|
|
|
|
Further optimizations are possible but not required.
|
2016-12-05 22:15:40 +01:00
|
|
|
|
<br><br>
|
