Monthly Archives: July 2017

Fast Fourier Transform Assume we have $n$ data points $x_0, x_1, \ldots, x_{n-1}$. For convenience, assume $n$ is a power of two; if it’s different, we can just pad with zeroes. We want to efficiently compute the transformed sequence $y_k … Continue reading →