Next: Make it recursive
Up: Assignment 10: Fast Fourier
Previous: Assignment 10: Fast Fourier
- 1.
- Last time you wrote commands to split a signal into even and odd
elements, calculate the DFT of the two halves, and then zip the
demi-DFTs into the DFT of the whole. Take those commands and
encapsulate them in a procedure named fft. The procedure should
take the signal (and array of floating-point numbers) and the number
of elements as arguments, just like dft. It should calculate
and return an array of complex numbers.
- 2.
- Give some thought to proper encapsulation, which means that your
procedure should not modify or read any global variables. It should
only read its arguments, and all other variables should be declared
local.
- 3.
- Use the time command to compare the run times of dft
and fft for the same data (and make sure you get the same answer
in both cases). (Read the documentation of time carefully!)
Allen B. Downey
1998-11-30