Fast Fourier transform: Difference between revisions
Content added Content deleted
(→{{header|Common Lisp}}: Adapted to demonstrate CL features (also improving its performance to the O(nlogn) expected of an FFT algorithm)) |
m (→{{header|Common Lisp}}: Deleted a bit of unrelated code) |
||
| Line 652: | Line 652: | ||
#C(0.9999999999999999D0 0.4142135623730949D0) #C(0.0D0 0.0D0) |
#C(0.9999999999999999D0 0.4142135623730949D0) #C(0.0D0 0.0D0) |
||
#C(0.9999999999999997D0 2.414213562373095D0)) |
#C(0.9999999999999997D0 2.414213562373095D0)) |
||
=={{header|Crystal}}== |
|||
<lang ruby>def fft(x : Array(Float64)) : Array(Complex) |
|||
return [x[0].to_c] if x.size <= 1 |
|||
even = fft(Array.new(x.size / 2) { |k| x[2 * k] }) |
|||
odd = fft(Array.new(x.size / 2) { |k| x[2 * k + 1] }) |
|||
c = Array.new(x.size / 2) { |k| Complex.new(0, -2 * Math::PI * k / x.size).exp } |
|||
codd = Array.new(x.size / 2) { |k| c[k] * odd[k] } |
|||
return Array.new(x.size / 2) { |k| even[k] + codd[k] } + Array.new(x.size / 2) { |k| even[k] - codd[k] } |
|||
end</lang> |
|||
=={{header|D}}== |
=={{header|D}}== |
||