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.[ref]
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
For a power-of-two length, the radix-two Cooley-Tukey FFT algorithm has time complexity in arithmetic operations, compared with for evaluating every sum independently; these are Big O notation growth rates rather than machine timings. It returns the same eight coefficients in the example. In exact arithmetic this reorganization introduces no approximation; actual implementations still incur roundoff error.
Articles by others on the same topic
The Fast Fourier Transform (FFT) is an algorithm that computes the Discrete Fourier Transform (DFT) and its inverse efficiently. The DFT is a mathematical transformation used to analyze the frequency content of discrete signals, transforming a sequence of complex numbers into another sequence of complex numbers. The basic idea is to express a discrete signal as a sum of sinusoids, which can provide insights into the signal's frequency characteristics.
An efficient algorithm to calculate the discrete Fourier transform.