An electric guitar's pickup also catches the hum of the mains wiring. A sound engineer has a recording x of N samples and wants to know how strong one particular wave in it is: the wave that goes through exactly k whole cycles during the recording.
The tool for this is one bin of the discrete Fourier transform (DFT):
X[k] = sum over n = 0 .. N-1 of x[n] * exp(-2j * pi * k * n / N)
exp(-2j * pi * k * n / N) is a unit arrow (a complex number of length 1, real part cos, imaginary part sin of its angle) that turns backwards k times over the recording. Each sample is multiplied by the arrow at its moment, and the products are added. If the recording contains a wave that also turns k times, the products keep pointing the same way and pile up. Any other whole number of cycles, and any constant offset, makes them point all round the circle and cancel out. A wave a * cos(2 * pi * k * n / N + p) gives |X[k]| = a * N / 2, so its amplitude is
amplitude = 2 * |X[k]| / N
Write hum_bin(x, k) that returns a tuple (re, im, amplitude): the real and imaginary parts of X[k] and the amplitude. Use cmath.exp, or math.cos and math.sin (exp(-1j * a) = cos(a) - 1j * sin(a)).
Examples
Input: x = [0, 1, 0, -1], k = 1
Output: (0.0, -2.0, 1.0)
Explanation: one cycle of a sine of amplitude 1. The arrows at n = 0..3 are 1, -1j, -1, 1j;
the products are 0, -1j, 0, -1j, adding up to -2j, and 2 * 2 / 4 = 1.
Input: x = [1, 0, -1, 0, 1, 0, -1, 0], k = 2
Output: (4.0, 0.0, 1.0)
Input: x = [2, 2, 2, 2, 2, 2], k = 1
Output: (0.0, 0.0, 0.0)
Explanation: a constant voltage has no wave that turns once.
Constraints
1 <= k < N / 2- answers are compared with a tolerance of
1e-6; values like1e-16for 0 count as correct
Goals
- Compute one bin of the DFT from its formula
- See a DFT bin as the signal multiplied by a turning arrow and added up
- Turn the size of a bin into the amplitude of the wave it measures