4,494
edits
Fast Fourier transform: Difference between revisions
Jump to navigation
Jump to search
no edit summary
mNo edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
The '''fast Fourier transform''' ('''FFT''') is an algorithm to compute the discrete Fourier transform of a [[vector]] in time <math>O(n log(n))</math>, where a naive implementation achieves only <math>O(n^2)</math> time. APL implementations of the fast Fourier transform began appearing as early as 1970, with an 8-line implementation by Alan R. Jones published in [[APL Quote-Quad]].<ref>Jones, Alan R. ([[IBM]]). "Fast Fourier transform". [[APL Quote-Quad]] Volume 1, Number 4. 1970-01.</ref> | The '''[[wikipedia:fast Fourier transform|fast Fourier transform]]''' ('''FFT''') is an algorithm to compute the [[wikipedia:discrete Fourier transform|discrete Fourier transform]] of a [[vector]] in time <math>O(n log(n))</math>, where a naive implementation achieves only <math>O(n^2)</math> time. APL implementations of the fast Fourier transform began appearing as early as 1970, with an 8-line implementation by Alan R. Jones published in [[APL Quote-Quad]].<ref>Jones, Alan R. ([[IBM]]). "Fast Fourier transform". [[APL Quote-Quad]] Volume 1, Number 4. 1970-01.</ref> | ||
A Fourier Transform (FFT) is a method of calculating the frequency components in a data set — and the inverse FFT converts back from the frequency domain — 4 applications of the FFT rotates you round the complex plane and leaves you back with the original data. | A Fourier Transform (FFT) is a method of calculating the frequency components in a data set — and the inverse FFT converts back from the frequency domain — 4 applications of the FFT rotates you round the complex plane and leaves you back with the original data. | ||
== Implementations == | |||
=== APLX === | |||
This FFT code is implemented with the [[wikipedia:Cooley–Tukey FFT algorithm|Cooley–Tukey FFT algorithm]] by dividing the transform into two pieces of size <source lang=apl inline>N÷2</source> at each step. It will run under [[APLX]]. | |||
This is as given in Robert J. Korsan's article in APL Congress 1973, p 259-268, with just line labels and a few comments added. | This is as given in Robert J. Korsan's article in APL Congress 1973, p 259-268, with just line labels and a few comments added. | ||
| Line 35: | Line 31: | ||
done:Z←⍉(N,2)⍴(+⌿X),[O-0.5]-⌿X | done:Z←⍉(N,2)⍴(+⌿X),[O-0.5]-⌿X | ||
</source> | </source> | ||
=== Dyalog APL === | |||
FFT appears in [[dfns.dws]], a [[workspace]] supplied with [[Dyalog APL]], in the context of fast multi-digit multiplication<ref>dfns.dws: [http://dfns.dyalog.com/n_xtimes.htm xtimes] — Fast multi-digit product using FFT</ref>. Extracted from there, it is there defined as: | |||
<source lang=apl> | |||
roots←{×\1,1↓(⍵÷2)⍴¯1*2÷⍵} | |||
cube←{⍵⍴⍨2⍴⍨2⍟⍴⍵} | |||
floop←{(⊣/⍺)∇⍣(×m)⊢(+⌿⍵),[m-0.5]⍺×[⍳m←≢⍴⍺]-⌿⍵} | |||
FFT←{,(cube roots⍴⍵)floop cube ⍵} | |||
</source> | |||
== References == | == References == | ||
<references /> | <references /> | ||