Implement the Discrete Fourier Transform (DFT) for a sequence of any length. This may implemented as either a function or a program and the sequence can be given as either an argument or using standard input.
The algorithm will compute a result based on standard DFT in the forward direction. The input sequence has length
N and consists of
[x(0), x(1), ..., x(N-1)]. The output sequence will have the same length and consists of
[X(0), X(1), ..., X(N-1)] where each
X(k) is defined by the relation below.
- This is code-golf so the shortest solution wins.
- Builtins that compute the DFT in forward or backward (also known as inverse) directions are not allowed.
- Floating-point inaccuracies will not be counted against you.
DFT([1, 1, 1, 1]) = [4, 0, 0, 0] DFT([1, 0, 2, 0, 3, 0, 4, 0]) = [10, -2+2j, -2, -2-2j, 10, -2+2j, -2, -2-2j] DFT([1, 2, 3, 4, 5]) = [15, -2.5+3.44j, -2.5+0.81j, -2.5-0.81j, -2.5-3.44j] DFT([5-3.28571j, -0.816474-0.837162j, 0.523306-0.303902j, 0.806172-3.69346j, -4.41953+2.59494j, -0.360252+2.59411j, 1.26678+2.93119j] = [2, -3j, 5, -7j, 11, -13j, 17]
There was a previous challenge for finding the DFT using a FFT algorithm for sequences with lengths equal to a power of 2. You may find some tricks there that might help you here. Keep in mind that this challenge does not limit you to any complexity and also requires your solution to work for sequences of any length.