DFT (Discrete Fourier Transform) Algorithm in Swift

I am looking to replicate in Swift what the FFT function does in Matlab. Essentially, it takes an arbitrary length signal (not necessarily a multiple of \$2^n\$) and gives real and complex DFT coefficients.

Since the FFT described in Accelerate can only handle sample sizes that are multiples of \$2^n\$, I wrote a brute force algorithm in Swift that produces exactly the same results as the Matlab FFT function for arbitrary sample size.

The problem: When my sample size > 15,000 sample (say), this algorithm takes about 20 s to complete. Could this be sped up?

import Foundation

public func fft(x: [Double]) -> ([Double],[Double]) {

    let N = x.count
    var Xre: [Double] = Array(repeating:0, count:N)
    var Xim: [Double] = Array(repeating:0, count:N)

    for k in 0..<N
    {
        Xre[k] = 0
        Xim[k] = 0
        for n in 0..<N {
            let q = (Double(n)*Double(k)*2.0*M_PI)/Double(N)
            Xre[k] += x[n]*cos(q) // Real part of X[k]
            Xim[k] -= x[n]*sin(q) // Imag part of X[k]
        }
    }
    return (Xre, Xim)
}

// Call FFT
let x: [Double] = [1, 2, 3, 4, 5, 6] // works rapidly
// let x = Array(stride(from: 0, through: 15000, by: (1.0))) // Will   choke it
let (fr, fi) = fft (x: x)
print("Real:", fr)
print(" ")
print("Imag:", fi)
// Call FFT

I think your code is doing DFT (Discrete Fourier Transform) and not FFT. You are doing \$O(n^{2})\$ operations in the 2 for loops. The FFT is supposed to be \$n*\log(n)\$.

First thing to do is remove repeated multiplications. The terms Double(n)2M_PI/Double(N) can be calculated (as initial step) for every \$n\$ in \$0:(N-1)\$. Make a map for each \$n\$ to this value and use it to calculate \$q\$.

Then, see if using properties of \$\sin(2x)\$, \$\sin(\frac{x}{2})\$, \$\cos(2x)\$, \$\cos(\frac{x}{2})\$, etc. are faster than actually calling those functions.

For example:

$$\begin{align}
\sin(2x) &= 2\sin(x)\cos(x) \\
\cos(2x) &= \cos^{2}(x) - \sin^{2}(x)
\end{align}
$$

or

$$\begin{align}
\sin\left(\frac{x}{2}\right) &= \sqrt{\frac{1-\cos(x)}{2}} \\
\cos\left(\frac{x}{2}\right) &= \sqrt{\frac{1+\cos(x)}{2}}
\end{align}
$$

If these are faster, you will reduce the complexity significantly.

StackExchange Code Review Q#154036, answer score: 7