# Difference between revisions of "Fast Fourier transform"

(Reference for early Quote Quad implementation) |
|||

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

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

## Latest revision as of 09:47, 24 March 2020

The **fast Fourier transform** (**FFT**) is an algorithm to compute the discrete Fourier transform of a vector in time , where a naive implementation achieves only 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.^{[1]}

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 Cooley–Tukey FFT algorithm by dividing the transform into two pieces of size `N÷2`

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.

- X and Z are two-row matrices representing the input and output real and imaginary data. The data length must be
`2*N`

(N integer), and the algorithm will cope with varying N, unlike many DSP versions which are for fixed N. - Zero frequency is at
`Z[1;]`

, maximum frequency in the middle; from there to`¯1↑[1] Z`

are negative frequencies. i.e. for an input Gaussian they transform a 'bath-tub' to a 'bath-tub'. - This is an elegant algorithm, and works by transforming the input data into an array of 2×2 FFT Butterflies.

```
Z←fft X;N;R;M;L;P;Q;S;T;O
⍝
⍝ Apl Congress 1973, p 267. Robert J. Korsan.
⍝
⍝ Restructure as an array of primitive 2×2 FFT Butterflies
X←(2,R←(M←⌊2⍟N←¯1↑⍴X)⍴2)⍴⍉X
⍝ Build sin and cosine table :
Z←R⍴⍉2 1∘.○○(-(O←?1)-⍳P)÷P←N÷2
⍝
Q←⍳P←M-1+L←0
T←M-~O
loop:→(M≤L←L+1)⍴done
X←(+⌿X),[O+¯0.5+S←M-L](-/Z×-⌿X),[O+P-0.5]+/Z×⌽-⌿X
Z←(((-L)⌽Q),T)⍉R⍴((1+P↑(S-1)⍴1),2)↑Z
→loop
done:Z←⍉(N,2)⍴(+⌿X),[O-0.5]-⌿X
```

### Dyalog APL

FFT appears in dfns.dws, a workspace supplied with Dyalog APL, in the context of fast multi-digit multiplication^{[2]}. Extracted from there, it is there defined as:

```
roots←{×\1,1↓(⍵÷2)⍴¯1*2÷⍵}
cube←{⍵⍴⍨2⍴⍨2⍟⍴⍵}
floop←{(⊣/⍺)∇⍣(×m)⊢(+⌿⍵),[m-0.5]⍺×[⍳m←≢⍴⍺]-⌿⍵}
FFT←{,(cube roots⍴⍵)floop cube ⍵}
```

## References

- ↑ Jones, Alan R. (IBM). "Fast Fourier transform". APL Quote-Quad Volume 1, Number 4. 1970-01.
- ↑ dfns.dws: xtimes — Fast multi-digit product using FFT