Fast Fourier transform: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,929: / Line 1,929: @@
 {{trans|Python}}
 <lang nim>import math, complex, strutils
-proc toComplex(x: float): TComplex = result.re = x
-proc toComplex(x: TComplex): TComplex = x
 # Works with floats and complex numbers as input
-proc fft[T](x: openarray[T]): seq[TComplex] =
+proc fft[T: float | Complex[float]](x: openarray[T]): seq[Complex[float]] =
   let n = x.len
+  if n == 0: return
-  result = newSeq[TComplex]()
-  if n <= 1:
-    for v in x: result.add toComplex(v)
+  result.newSeq(n)
+  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: / Line 1,947: @@
   var (even, odd) = (fft(evens), fft(odds))
-  for k in 0 .. < n div 2:
+  let halfn = n div 2
-    result.add(even[k] + exp((0.0, -2*pi*float(k)/float(n))) * odd[k])
-  for k in 0 .. < n div 2:
+  for k in 0 .. < halfn:
-    result.add(even[k] - exp((0.0, -2*pi*float(k)/float(n))) * odd[k])
+    let a = exp(complex(0.0, -2 * Pi* float(k) / float(n))) * odd[k]
+    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]):