Encapsulate the divide, conquer, and glue

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!)