Fast Fourier transform: Difference between revisions
jq
(→{{header|Perl 6}}: minor simplification) |
(jq) |
||
Line 767:
}</lang>
=={{header|jq}}==
Currently jq has no support for complex numbers, so the following implementation uses [x,y] to represent the complex number x+iy.
====Complex number arithmetic====
<lang jq>
# multiplication of real or complex numbers
def cmult(x; y):
if (x|type) == "number" then
if (y|type) == "number" then [ x*y, 0 ]
else [x * y[0], x * y[1]]
end
elif (y|type) == "number" then cmult(y;x)
else [ x[0] * y[0] - x[1] * y[1], x[0] * y[1] + x[1] * y[0]]
end;
def cplus(x; y):
if (x|type) == "number" then
if (y|type) == "number" then [ x+y, 0 ]
else [ x + y[0], y[1]]
end
elif (y|type) == "number" then cplus(y;x)
else [ x[0] + y[0], x[1] + y[1] ]
end;
def cminus(x; y): cplus(x; cmult(-1; y));
# e(ix) = cos(x) + i sin(x)
def expi(x): [ (x|cos), (x|sin) ];</lang>
====FFT====
<lang jq>def fft:
length as $N
| if $N <= 1 then .
else ( [ .[ range(0; $N; 2) ] ] | fft) as $even
| ( [ .[ range(1; $N; 2) ] ] | fft) as $odd
| (1|atan * 4) as $pi
| [ range(0; $N/2) | cplus($even[.]; cmult( expi(-2*$pi*./$N); $odd[.] )) ] +
[ range(0; $N/2) | cminus($even[.]; cmult( expi(-2*$pi*./$N); $odd[.] )) ]
end;</lang>
Example:
<lang jq>[1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0] | fft
</lang>
{{Out}}
[[4,-0],[1,-2.414213562373095],
[0,0],[1,-0.4142135623730949],
[0,0],[0.9999999999999999,0.4142135623730949],
[0,0],[0.9999999999999997,2.414213562373095]]
=={{header|Julia}}==
Julia has a built-in FFT function:
| |||