← All problems
#39 Fast Fourier Transform Hard

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.

Implementation Requirements

Example 1:

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])

Example 2:

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])

Constraints

Guided walkthrough coming soon. Below is the official starter signature in each language; the clickable line-by-line explanation hasn't been authored yet.
Problem text & starters from the official AlphaGPU/leetgpu-challenges. Solve it on leetgpu.com.