2026/04/01 by Mohamed Amine Bergach · 1 voice · 1 citation
Computer Science · #cs.PF
paper · pdf · doi:10.48550/arxiv.2604.00567
The fused multiply-add (FMA) instruction enables the radix-2 FFT butterfly to be computed in 6~FMA operations -- the proven minimum. The classical factorization by Linzer and Feig~\citelinzer1993 precomputes the ratio \cotθ= cosθ/sinθ, which is singular when the twiddle factor is W0 = 1 (i.e., sinθ= 0). Standard practice clamps sinθ to a small epsilon, degrading numerical precision. We observe that an alternative factorization using cosθ as the outer multiplier (precomputing tanθ) avoids this particular singularity but introduces a new one at WN/4. We then propose a dual-select strategy that chooses, per twiddle factor, whichever factorization yields |ratio| ≤ 1. This eliminates all singularities, requires no epsilon clamping, and bounds the precomputed ratio to unity for all twiddle factors. For N = 1024, the worst-case ratio drops from 163 (Linzer-Feig) to exactly~1.0 (dual-select), yielding a 235× tighter error bound in FP16 arithmetic over 10~FFT passes. The strategy adds zero computational overhead -- only the precomputed twiddle table changes.