So the evaluations of Q and R at ω 0 to ω N-1 are enough. Observe that the value at ω k+N is very simply related to the value at ω k: We have f 0, f 1, f 2, …, f 2N-1, and we want to compute P(ω 0), P(ω 1), … P(ω 2N-1) where we can write
I'll replace N with 2N to simplify notation. Any such algorithm is called the fast Fourier transform. But we can exploit the special structure that comes from the ω's we chose, and that allows us to do it in O(N log N). Note that finding these F's naively takes O(N 2) operations. That is, for each n from 0 to N-1, the new number F n is P(ω n) = ∑ 0≤k≤N-1 f kω nk. The N new numbers F 0, F 1, …, F N-1 that the DFT gives are the results of evaluating the polynomial at powers of ω. You can think of the f k's as the coefficients of a polynomial P(x) = ∑f kx k. Specifically: Let ω be a primitive Nth root of 1 (either in the complex numbers or in some finite field), which means that ω N=1 but no smaller power is 1.
Given N numbers f 0, f 1, f 2, …, f N-1, the DFT gives a different set of N numbers. (Note that there are alternative interpretations, and other algorithms.) Discrete Fourier transform Here's the simplest explanation of the DFT and FFT as I think of them, and also examples for small N, which may help. You're right, "the" Fast Fourier transform is just a name for any algorithm that computes the discrete Fourier transform in O(n log n) time, and there are several such algorithms.
0 kommentar(er)
