Iterative In-Place Radix-2 Cooley-Tukey Fast Fourier Transform Algorithm with Bit-Reversal. The size of the input signal must be a power of 2. If it isn't then it is padded with zeros and the output FFT will be bigger than the input signal. More info: https://www.algorithm-archive.org/contents/
(ArrayList<Complex> x, boolean inverse)
| 193 | * @return |
| 194 | */ |
| 195 | public static ArrayList<Complex> fft(ArrayList<Complex> x, boolean inverse) { |
| 196 | /* Pad the signal with zeros if necessary */ |
| 197 | paddingPowerOfTwo(x); |
| 198 | int n = x.size(); |
| 199 | int log2n = findLog2(n); |
| 200 | x = fftBitReversal(n, log2n, x); |
| 201 | int direction = inverse ? -1 : 1; |
| 202 | |
| 203 | /* Main loop of the algorithm */ |
| 204 | for (int len = 2; len <= n; len *= 2) { |
| 205 | double angle = -2 * Math.PI / len * direction; |
| 206 | Complex wlen = new Complex(Math.cos(angle), Math.sin(angle)); |
| 207 | for (int i = 0; i < n; i += len) { |
| 208 | Complex w = new Complex(1, 0); |
| 209 | for (int j = 0; j < len / 2; j++) { |
| 210 | Complex u = x.get(i + j); |
| 211 | Complex v = w.multiply(x.get(i + j + len / 2)); |
| 212 | x.set(i + j, u.add(v)); |
| 213 | x.set(i + j + len / 2, u.subtract(v)); |
| 214 | w = w.multiply(wlen); |
| 215 | } |
| 216 | } |
| 217 | } |
| 218 | x = inverseFFT(n, inverse, x); |
| 219 | return x; |
| 220 | } |
| 221 | |
| 222 | /* Find the log2(n) */ |
| 223 | public static int findLog2(int n) { |