# The Dft And Fft

By the halving lemma, the list of values (30.10) consists not of *n* distinct values but only of the *n*/2 complex (*n*/2)th roots of unity, with each root occurring exactly twice. Therefore, the polynomials *A*^{[0]} and *A*^{[1]} of degree-bound *n*/2 are recursively evaluated at the *n*/2 complex (*n*/2)th roots of unity. These subproblems have exactly the same form as the original problem, but are half the size. We have now successfully divided an *n*-element DFT_{n} computation into two *n*/2-element DFT_{n/2} computations. This decomposition is the basis for the following recursive FFT algorithm, which computes the DFT of an *n*-element vector *a* = (*a*_{0}, *a*_{1},..., *a*_{n-1}), where *n* is a power of 2.

RECURSIVE-FFT(a) 1n←length[a] ▹nis a power of 2. 2ifn= 1 3then returna4w←_{n}eπi/n5w← 1 6a[0] ← (a0,a2,...,an-2) 7a[1] ← (a1,a3,...,an-1) 8y[0] ← RECURSIVE-FFT(a[0]) 9y[1] RECURSIVE-FFT(a[1]) 10fork← 0ton/2 - 1 11do

12

13w←w w14_{n}returny▹yis assumed to be a column vector.

The RECURSIVE-FFT procedure works as follows. Lines 2 -3 represent the basis of the recursion; the DFT of one element is the element itself, since in this case

Lines 6 -7 define the coefficient vectors for the polynomials *A*^{[0]} and *A*^{[1]}. Lines 4, 5, and 13 guarantee that *w* is updated properly so that whenever lines 11 -12 are executed, . (Keeping a running value of *w* from iteration to iteration saves time over computing from scratch each time through the **for** loop.) Lines 8-9 perform the recursive DFT_{n/2} computations, setting, for *k* = 0, 1,..., *n*/2 - 1,

or, since by the cancellation lemma,

Lines 11-12 combine the results of the recursive DFT_{n/2} calculations. For *y*_{0}, *y*_{1},..., *y*_{n/2-1}, line 11 yields

For *y*_{n/2}, *y*_{n/2 1},..., *y*_{n-1}, letting *k* = 0, 1,..., *n*/2 - 1, line 12 yields

Thus, the vector *y* returned by RECURSIVE-FFT is indeed the DFT of the input vector *a*.