Porting CUDA FFT to Mojo: Achieving Bit-Exact Precision (www.msuiche.com)

Porting a CUDA FFT to Mojo for the LeetGPU challenge exposed that the bottleneck wasn’t the FFT math itself but tiny differences in sinf()/cosf() behavior and accumulation precision. Mojo’s stdlib used fast PTX approximations (sin.approx.ftz.f32 / cos.approx.ftz.f32), producing a max absolute mismatch of 0.023 vs CUDA. Reimplementing CUDA’s libdevice approach (Payne–Hanek range reduction, three-part Cody–Waite reduction, minimax polynomials and round-to-even via PTX cvt.rni.s32.f32) reduced the error to 2^-9 (0.001953125) but still missed the 1e-3 tolerance because millions of twiddle-factor evaluations and parallel reduction ordering amplified tiny differences. The final, deterministic fix was to perform all angle math, twiddle generation, complex multiplications and accumulations in Float64 (with Kahan summation), only casting back to Float32 at output. PTX disassembly confirmed CUDA’s exact sequence (mul by 2/π, round-to-nearest-even, three FMAs splitting π/2), which must be matched to reproduce bit-exact results. Significance: achieving bit-exact GPU-porting requires matching range-reduction algorithms, rounding modes, and accumulation precision — fast approximate intrinsics and Float32 accumulation can cause catastrophic error growth in large FFTs. The result: a Mojo FFT that bit-for-bit matches CUDA for N up to 262,144.