Fast Fourier Transforms Part 3: Bluestein’s Algorithm (connorboyle.io)
from cascadianblue@programming.dev to programming@programming.dev on 05 May 04:15
https://programming.dev/post/49881685

The Cooley-Tukey fast Fourier transform can compute discrete Fourier transforms efficiently for signals of highly-composite length, such as powers of 2. However, to compute signal lengths with large prime factors, an algorithm such as Bluestein’s is needed to prevent the algorithm from degenerating to quadratic complexity.

Thanks to Bluestein’s algorithm, FFTs of prime-length input sequences are “only” ~4-6x slower than nearby powers of 2. The clunkiness of Bluestein’s makes fast Fourier transforms interesting: the steps to complete the algorithm is not a monotonic function of the problem size, shooting up and down depending on the factors of the input length.

Interestingly, I found that almost no signal processing knowledge is required to understand and derive Bluestein’s algorithm; anyone with general computing knowledge can follow along and should be able to implement Bluestein’s algorithm after reading this post.

#programming