FFT in C with floating point 
FFT (see CoffeeBreak 1, 2) is very old algorithm, may be more than 40 years
old. Therefore a lot of C source codes are spread around the world. First
of all, let's try it normally in C with floating point. 
(1) What's FFT?? Any complicated wave can be decomposed to simple sine waves... This theory, Fourier Transform, is discovered by French mathematician Joseph Fourier. DFT(Discrete Fourier Transform) is to do it in digital and FFT(Fast Fourier Transform) is to speed it up. (2) Speed up by decreasing multiplications FFT is the algorithm that factorizes ab+ac to a(b+c) to decrease its multiplications. The number of complex multiplications becomes (N/2)log2(N) whereas it's N^2 in DFT. The following table shows number of multiplications.


(1) Describe floating point FFT  


(2) Execute floating point FFT  


(3) Inspect the Result of FFT  


