Problem 558472 · medium · Level 05 Advanced Algorithms & Graphs

The Gearbox Analyser's Fast Transform

fast Fourier transform · recursion · divide and conquer · discrete Fourier transform · complex numbers

A handheld analyser listens to the gearbox of a wind turbine, N samples at a time, and shows the spectrum. Its discrete Fourier transform is

X[k] = sum over n = 0 .. N-1 of  x[n] * exp(-2j * pi * k * n / N)        for k = 0 .. N-1

Computed straight from the formula, that is N * N complex multiplications: about 268 million for N = 16384, far too slow for a small battery-powered device (and for this problem). The fast Fourier transform (FFT) gets exactly the same numbers much faster when N is a power of two, by splitting the work in half again and again:

  • Put the even-numbered samples x[0], x[2], x[4], ... in one list and the odd-numbered ones x[1], x[3], ... in another. Each has N / 2 samples; compute the transform of each, E and O (the same job, half the size).
  • For k = 0 .. N/2 - 1, with the twiddle factor t = exp(-2j * pi * k / N) * O[k]:
X[k]         = E[k] + t
X[k + N / 2] = E[k] - t
  • The transform of a single sample is that sample itself.

Each level of splitting costs about N operations and there are log2(N) levels, so N = 16384 takes a few hundred thousand steps instead of 268 million.

Write fft(x) that returns the list of the N complex numbers X[0], ..., X[N-1]. With Run, compare your result with the formula on a short list to convince yourself, and press plot([abs(v) for v in fft(x)], kind="stem") to see the spectrum. The tests show your answer as (real, imag) pairs.

Examples

Input:  x = [1, 2, 3, 4]
Output: [(10.0, 0.0), (-2.0, 2.0), (-2.0, 0.0), (-2.0, -2.0)]      (as (real, imag) pairs)
Explanation: the even samples [1, 3] transform to E = [4, -2], the odd [2, 4] to O = [6, -2].
k = 0: t = 6, so X[0] = 10 and X[2] = -2. k = 1: t = -1j * -2 = 2j, so X[1] = -2 + 2j and X[3] = -2 - 2j.

Input:  x = [5]
Output: [(5.0, 0.0)]

Constraints

  • N = len(x) is a power of two, 1 <= N <= 2**14; values are ints or floats
  • return complex numbers (Python's complex); answers are compared with a tolerance of 1e-6, so values like 1e-16 where the exact answer is 0 are fine

Goals

  • Split a recording into its even and odd samples and transform each half
  • Combine the two half-spectra with twiddle factors into the full spectrum
  • See why this takes about N log2 N steps instead of N squared
Starting Python…