DFT of Small Series

Problem

Compute the discrete Fourier transform of a series. For each frequency k = 0, ..., n-1 compute X[k] = sum over t of x[t] * exp(-2*pi*i*k*t/n), represented as the pair [real, imaginary].

Return a list of n such pairs.

Hint

The k = 0 bin is the sum of the series; negative imaginary parts come from the -sin term.

Test cases

case 1

in: [[1,0,0,0]]

expected: [[1,0],[1,0],[1,0],[1,0]]

case 2

in: [[1,1,1,1]]

expected: [[4,0],[-1.224646799147353e-16,-1.2246467991473532e-16],[0,-2.449293598294706e-16],[3.67394039744206e-16,-3.6739403974420594e-16]]

case 3

in: [[1,2,3,4]]

expected: [[10,0],[-2.0000000000000004,1.9999999999999996],[-2,-9.797174393178826e-16],[-1.9999999999999982,-2.000000000000001]]

Starter codePython

import math
def dft(series):
    # Your code here
    pass

3 test cases · run your code against them in the editor