Fast Fourier transform: Difference between revisions
Jump to navigation
Jump to search
m (2 revisions imported: Migrate from miraheze) |
(Reference for early Quote Quad implementation) |
||
| 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. | 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> | ||
See [[wikipedia:FFT|fast Fourier transform]] and [[wikipedia:Discrete Fourier transform|Discrete Fourier transform]] on Wikipedia. | See [[wikipedia:FFT|fast Fourier transform]] and [[wikipedia:Discrete Fourier transform|Discrete Fourier transform]] on Wikipedia. | ||
| Line 35: | Line 35: | ||
done:Z←⍉(N,2)⍴(+⌿X),[O-0.5]-⌿X | done:Z←⍉(N,2)⍴(+⌿X),[O-0.5]-⌿X | ||
</source> | </source> | ||
== References == | |||
<references /> | |||