Editing Fast Fourier transform (section)

==Algorithms==

===Cooley–Tukey algorithm===
{{Main|Cooley–Tukey FFT algorithm}}

By far the most commonly used FFT is the Cooley–Tukey algorithm. This is a [[divide-and-conquer algorithm]] that [[recursively]] breaks down a DFT of any [[composite number|composite]] size <math display="inline">n = n_1n_2</math> into <math display="inline">n_1</math> smaller DFTs of size <math display="inline">n_2</math>, along with <math>O(n)</math> multiplications by complex [[roots of unity]] traditionally called [[twiddle factor]]s (after Gentleman and Sande, 1966).<ref name="Gentleman_Sande_1966"/>

This method (and the general idea of an FFT) was popularized by a publication of Cooley and Tukey in 1965,<ref name="Cooley_Tukey_1965"/> but it was later discovered<ref name="Heideman_Johnson_Burrus_1984"/> that those two authors had together independently re-invented an algorithm known to [[Carl Friedrich Gauss]] around 1805<ref name="Gauss_1805"/> (and subsequently rediscovered several times in limited forms).

The best known use of the Cooley–Tukey algorithm is to divide the transform into two pieces of size {{math|n/2}} at each step, and is therefore limited to power-of-two sizes, but any factorization can be used in general (as was known to both Gauss and Cooley/Tukey<ref name="Heideman_Johnson_Burrus_1984"/>). These are called the ''radix-2'' and ''mixed-radix'' cases, respectively (and other variants such as the [[split-radix FFT]] have their own names as well).  Although the basic idea is recursive, most traditional implementations rearrange the algorithm to avoid explicit recursion. Also, because the Cooley–Tukey algorithm breaks the DFT into smaller DFTs, it can be combined arbitrarily with any other algorithm for the DFT, such as those described below.

===Other FFT algorithms===
{{Main|Prime-factor FFT algorithm|Bruun's FFT algorithm|Rader's FFT algorithm|Chirp Z-transform|hexagonal fast Fourier transform}}

There are FFT algorithms other than Cooley–Tukey.

For <math display="inline">n = n_1n_2</math> with [[coprime]] <math display="inline">n_1</math> and <math display="inline">n_2</math>, one can use the [[Prime-factor FFT algorithm|prime-factor]] (Good–Thomas) algorithm (PFA), based on the [[Chinese remainder theorem]], to factorize the DFT similarly to Cooley–Tukey but without the twiddle factors. The Rader–Brenner algorithm (1976)<ref name="Brenner_Rader_1976"/> is a Cooley–Tukey-like factorization but with purely imaginary twiddle factors, reducing multiplications at the cost of increased additions and reduced [[numerical stability]]; it was later superseded by the [[split-radix]] variant of Cooley–Tukey (which achieves the same multiplication count but with fewer additions and without sacrificing accuracy). Algorithms that recursively factorize the DFT into smaller operations other than DFTs include the Bruun and [[Quick Fourier transform algorithm|QFT]] algorithms. (The Rader–Brenner<ref name="Brenner_Rader_1976"/> and QFT algorithms were proposed for power-of-two sizes, but it is possible that they could be adapted to general composite {{mvar|n}}. Bruun's algorithm applies to arbitrary even composite sizes.) [[Bruun's FFT algorithm|Bruun's algorithm]], in particular, is based on interpreting the FFT as a recursive factorization of the [[polynomial]] <math>z^n-1</math>, here into real-coefficient polynomials of the form <math>z^m-1</math> and <math>z^{2m} + az^m + 1</math>.

Another polynomial viewpoint is exploited by the Winograd FFT algorithm,<ref name="Winograd_1978"/><ref name="Winograd_1979"/> which factorizes <math>z^n-1</math> into [[cyclotomic polynomial]]s—these often have coefficients of 1,&nbsp;0,&nbsp;or&nbsp;−1, and therefore require few (if any) multiplications, so Winograd can be used to obtain minimal-multiplication FFTs and is often used to find efficient algorithms for small factors. Indeed, Winograd showed that the DFT can be computed with only <math>O(n)</math> irrational multiplications, leading to a proven achievable lower bound on the number of multiplications for power-of-two sizes; this comes at the cost of many more additions, a tradeoff no longer favorable on modern [[central processing unit|processors]] with [[floating-point unit|hardware multipliers]]. In particular, Winograd also makes use of the PFA as well as an algorithm by Rader for FFTs of ''prime'' sizes.

[[Rader's FFT algorithm|Rader's algorithm]], exploiting the existence of a [[generating set of a group|generator]] for the multiplicative [[group (mathematics)|group]] modulo prime {{mvar|n}}, expresses a DFT of prime size {{mvar|n}} as a cyclic [[convolution]] of (composite) size {{math|''n'' – 1}}, which can then be computed by a pair of ordinary FFTs via the [[convolution theorem]] (although Winograd uses other convolution methods). Another prime-size FFT is due to L. I. Bluestein, and is sometimes called the [[chirp-z algorithm]]; it also re-expresses a DFT as a convolution, but this time of the ''same'' size (which can be zero-padded to a [[power of two]] and evaluated by radix-2 Cooley–Tukey FFTs, for example), via the identity

: <math>nk = -\frac{(k-n)^2} 2 + \frac{n^2} 2 + \frac{k^2} 2.</math>

[[Hexagonal fast Fourier transform]] (HFFT) aims at computing an efficient FFT for the hexagonally-sampled data by using a new addressing scheme for hexagonal grids, called Array Set Addressing (ASA).