Next: About this document ...
Up: Assignment 10: Fast Fourier
Previous: Make it recursive
This step is optional.
- 1.
- It is often the case with recursive things that we don't
really want to recurse all the way down to the silly case where
we take the DFT of a single element. Rather, once we get to
something small, we go ahead and calculate it directly, using
dft.
- 2.
- Modify your base case so that if N>2 it recurses, but
when N=2 it calculates the DFT directly. Compare the run time to
the original version. Experiment with different threshold values
and find the optimum.
Allen B. Downey
1998-11-30