Fast Fourier Transform - due Friday, March 10

Write a program to compute the discrete Fourier transform of 2^m points using the fast Fourier transform algorithm. Let ${\cal F}(x)$ denote the discrete Fourier transform of the vector x. Use the program to compute ${\cal F}(x)$ for the following vectors:

(a)

x=(1,2,3,4,5,6,7,8)

(b)

${\cal F}(x)$, where x=(1,2,3,4,5,6,7,8)

(c)

x=(1,-1,2,-2,3,-3,4,-4)

I will give a handout describing an FFT algorithm.