= Fast Fourier transform
{c}
{wiki}
= FFT
{c}
{synonym}
A <Fast Fourier transform> is an efficient <algorithm> for computing the <discrete Fourier transform> or <inverse discrete Fourier transform>. The <discrete Fourier transform> specifies the mathematical result; a <Fast Fourier transform> specifies how to compute it. Different <Fast Fourier transform> <algorithms> reorganize the same finite sums, with the selected sign and normalization. The <Cooley-Tukey FFT algorithm> is one important family of <Fast Fourier transforms>, using factorization of the record length.https://ocw.mit.edu/courses/6-02-introduction-to-eecs-ii-digital-communication-systems-fall-2012/06d7972059805d20e6a7db3a52ec23f2_MIT6_02F12_chap13.pdf[Balakrishnan, Terman, and Verghese, MIT 6.02 notes, §13.2.6, p. 194: the FFT computes the existing transform, 2012]{ref}
For a power-of-two length, the radix-two <Cooley-Tukey FFT algorithm> has <time complexity> $O(N\log N)$ in arithmetic operations, compared with $O(N^2)$ for evaluating every sum independently; these are <Big O notation> growth rates rather than machine timings. It returns the same eight <coefficients> $(8,4,-2i,0,0,0,2i,4)$ in the example. In exact arithmetic this reorganization introduces no approximation; actual implementations still incur <roundoff error>.
Back to article page
