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?