8.3. Exercises#

Exercise 8.1

Imagine that you want to optimize the radix-2 method to only compute the positive frequencies (i.e., like np.fft.rfft). How would you change the method?

Exercise 8.2

If you have an input \(N = 3^k\) (for some integer \(k\)), how would you modify the radix-2 algorithm to get a radix-3 algorithm?

  1. How many recursive calls will the FFT function need to make?

  2. What should the sub-problems represent, if not “even”- and “odd”-indexed signals?

  3. How would you define the “twiddle” factors for combining the results of recursive calls?