Fast Fourier transform: Difference between revisions
Content added Content deleted
Line 1,929:
{{trans|Python}}
<lang nim>import math, complex, strutils
# Works with floats and complex numbers as input
proc fft[T: float | Complex[float]](x: openarray[T]): seq[
let n = x.len
▲ if n <= 1:
if n == 1:
result[0] = (when T is float: complex(x[0]) else: x[0])
return
var evens, odds = newSeq[T]()
for i, v in x:
Line 1,946 ⟶ 1,947:
var (even, odd) = (fft(evens), fft(odds))
for k in 0 .. <
result[k] = even[k] + a
result[k + halfn] = even[k] - a
for i in fft(@[1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0]):
|