Implement a GPU program that computes the Fast Fourier Transform (FFT) of a
complex-valued 1-D signal. Given an input signal array containing
N complex numbers stored as interleaved real/imaginary pairs,
compute the discrete Fourier transform and store the result in the
spectrum array. The FFT converts a time-domain signal into its
frequency-domain representation using the formula: \[ X_k = \sum_{n=0}^{N-1}
x_n \cdot e^{-j 2\pi kn / N} \quad \text{for } k = 0, 1, \ldots, N-1 \] The
FFT algorithm reduces the computational complexity from O(N²) to O(N log N) by
exploiting symmetries in the twiddle factors.
solve function signature must remain unchangedspectrum array[real₀, imag₀, real₁, imag₁, ...]
Input: N = 4
signal = [1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
(represents: [1+0j, 0+0j, 0+0j, 0+0j])
Output: spectrum = [1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0]
(represents: [1+0j, 1+0j, 1+0j, 1+0j])
Input: N = 2
signal = [1.0, 0.0, 1.0, 0.0]
(represents: [1+0j, 1+0j])
Output: spectrum = [2.0, 0.0, 0.0, 0.0]
(represents: [2+0j, 0+0j])
1 ≤ N ≤ 262,1442 × NN = 262,144