Fast Fourier transform: Difference between revisions

Jump to navigation Jump to search
no edit summary
(Reference for early Quote Quad implementation)
No edit summary
(One intermediate revision by the same user not shown)
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>


See [[wikipedia:FFT|fast Fourier transform]] and [[wikipedia:Discrete Fourier transform|Discrete Fourier transform]] on Wikipedia.
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 ===
In this page the FFT is implemented with the [[wikipedia:FFT#Cooley–Tukey algorithm|Cooley–Tukey algorithm]] by dividing the transform into two pieces of size <source lang=apl inline>N÷2</source> at each step.
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]].
 
== APLX FFT Code ==
 
Note that [[APLX]] is no longer under development.


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 />

Navigation menu