Fast Fourier transform: Difference between revisions

Content added Content deleted

Inline

@@ Line 3,285: / Line 3,285: @@
   | -2            2 |
   +-----------------+</pre>
+=={{header|Swift}}==
+{{libheader|Swift Numerics}}
+{{trans|Kotlin}}
+<lang swift>import Foundation
+import Numerics
+typealias Complex = Numerics.Complex<Double>
+extension Complex {
+  var exp: Complex {
+    Complex(cos(imaginary), sin(imaginary)) * Complex(cosh(real), sinh(real))
+  }
+  public var pretty: String {
+    let real2 = real != -0 ? real : 0.0
+    let imag = imaginary != -0 ? imaginary : 0.0
+    let fmt = { String(format: "%.3f", $0) }
+    let result =
+      (imag >= 0 ? "\(fmt(real2)) + \(fmt(imag))i" : "\(fmt(real2)) - \(fmt(-imag))i")
+        .replacingOccurrences(of: ".0 ", with: " ")
+        .replacingOccurrences(of: ".0i", with: "i")
+        .replacingOccurrences(of: " + 0i", with: "")
+    if result.hasPrefix("0 ") {
+      return result
+        .replacingOccurrences(of: "0 ", with: "")
+        .replacingOccurrences(of: " ", with: "")
+    } else {
+      return result
+    }
+  }
+}
+func fft(_ array: [Complex]) -> [Complex] { _fft(array, direction: Complex(0.0, 2.0), scalar: 1) }
+func rfft(_ array: [Complex]) -> [Complex] { _fft(array, direction: Complex(0.0, -2.0), scalar: 2) }
+private func _fft(_ arr: [Complex], direction: Complex, scalar: Double) -> [Complex] {
+  guard arr.count > 1 else {
+    return arr
+  }
+  let n = arr.count
+  let cScalar = Complex(scalar, 0)
+  precondition(n % 2 == 0, "The Cooley-Tukey FFT algorithm only works when the length of the input is even.")
+  var evens = [Complex]()
+  var odds = [Complex]()
+  for i in 0..<n {
+    if i & 1 == 1 {
+      odds.append(arr[i])
+    } else {
+      evens.append(arr[i])
+    }
+  }
+  evens = _fft(evens, direction: direction, scalar: scalar)
+  odds = _fft(odds, direction: direction, scalar: scalar)
+  let pairs = (0 ..< n / 2).map({i -> (Complex, Complex) in
+    let offset = (direction * Complex((.pi * Double(i) / Double(n)), 0)).exp * odds[i] / cScalar
+    let base = evens[i] / cScalar
+    return (base + offset, base - offset)
+  })
+  var left = [Complex]()
+  var right = [Complex]()
+  for (l, r) in pairs {
+    left.append(l)
+    right.append(r)
+  }
+  return left + right
+}
+let dat = [Complex(1.0, 0.0), Complex(1.0, 0.0), Complex(1.0, 0.0), Complex(1.0, 0.0),
+           Complex(0.0, 0.0), Complex(0.0, 2.0), Complex(0.0, 0.0), Complex(0.0, 0.0)]
+print(fft(dat).map({ $0.pretty }))
+print(rfft(f).map({ $0.pretty }))</lang>
+{{out}}
+<pre>["4.000 + 2.000i", "2.414 + 1.000i", "-2.000 + 0.000i", "2.414 + 1.828i", "0.000 - 2.000i", "-0.414 + 1.000i", "2.000 - 0.000i", "-0.414 - 3.828i"]
+["1.000 + 0.000i", "1.000 + 0.000i", "1.000 + 0.000i", "1.000 + 0.000i", "0.000 + 0.000i", "0.000 + 2.000i", "0.000 - 0.000i", "0.000 + 0.000i"]</pre>
 =={{header|SystemVerilog}}==