Compute the Discrete Fourier Transform
Python 3, 77 bytes
lambda x,e=enumerate:[sum(t/1j**(4*k*n/len(x))for n,t in e(x))for k,_ in e(x)]
Test it on Ideone.
The code uses the equivalent formula
J, 30 20 bytes
3 bytes thanks to @miles.
Uses the fact that e^ipi = -1
.
The formula becomes X_k = sum(x_n / ((-1)^(2nk/N)))
.
+/@:%_1^2**/~@i.@#%#
Usage
>> DCT =: +/@:%_1^2**/~@i.@#%#
>> DCT 1 2 3 4 5
<< 15 _2.5j3.44095 _2.5j0.812299 _2.5j_0.812299 _2.5j_3.44095
where >>
is STDIN and <<
is STDOUT.
"Floating-point inaccuracies will not be counted against you."
MATL, 20 16 bytes
-1yn:qt!Gn/E*^/s
Input is a column vector, i.e. use semicolon as separator:
[1; 1; 1; 1]
[1; 0; 2; 0; 3; 0; 4; 0]
[1; 2; 3; 4; 5]
[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]
This uses the formula in Leaky Nun's answer, based on the facts that exp(iπ) = −1, and that MATL's power operaton with non-integer exponent produces (as in most programming languages) the principal branch result.
Try it online!
Due to Octave's weird spacing when displaying complex numbers, the real and imaginary parts in each entry of the output are separated by a space, as are consecutive entries. If that looks too ugly, add a !
at the end of the code (17 bytes) to have each entry of the output on a different line.
Explanation
-1 % Push -1
y % Get input implicitly. Push a copy below and one on top of -1
n:q % Row vector [0 1 ... N-1] where N is implicit input length
t! % Duplicate and transpose: column vector
Gn % Push input length
/ % Divide
E % Multiply by 2
* % Multiply, element-wise with broadcast. Gives the exponent as a matrix
^ % Power (base is -1), element-wise. Gives a matrix
/ % Divide matrix by input (column vector), element-wise with broadcast
s % Sum