Dual-Select FMA Butterfly for FFT: Eliminating Twiddle Factor Singularities with Bounded Precomputed Ratios Mohamed Amine Bergach Abstract 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 [ 1 ] precomputes the ratio cot ⁡ θ = cos ⁡ θ / sin ⁡ θ \cot\theta=\cos\theta/\sin\theta , which is singular when the twiddle factor is W 0 = 1 W^{0}=1 (i.e., sin ⁡ θ = 0 \sin\theta=0 ). Standard practice clamps sin ⁡ θ \sin\theta to a small epsilon, degrading numerical precision. We observe that an alternative factorization using cos ⁡ θ \cos\theta as the outer multiplier (precomputing tan ⁡ θ \tan\theta ) avoids this particular singularity but introduces a new one at W N / 4 W^{N/4} . We then propose a dual-select strategy that chooses, per twiddle factor, whichever factorization yields | ratio | ≤ 1 |\text{ratio}|\leq 1 . This eliminates all singularities, requires no epsilon clamping, and bounds the precomputed ratio to unity for all twiddle factors. For N = 1024 N=1024 , the worst-case ratio drops from 163 (Linzer-Feig) to exactly 1.0 (dual-select), yielding a 235 × 235\times tighter error bound in FP16 arithmetic over 10 FFT passes. The strategy adds zero computational overhead—only the precomputed twiddle table changes. I Introduction The radix-2 FFT butterfly computes, for inputs a,b\in\mathbb{C} and twiddle factor W=\omega_{r}+j\omega_{i}=e^{-j2\pi k/N} : \displaystyle A \displaystyle=a+Wb,\quad B=a-Wb. (1) Expanding into real and imaginary parts yields 10 floating-point operations (4 multiplications and 6 additions). On architectures with a fused multiply-add (FMA) instruction that computes a+b\times c in a single operation with one rounding, Linzer and Feig [ 1 ] showed that the butterfly can be refactored into exactly 6 FMA operations—the proven minimum. Subsequent work by Goedecker [ 2 ] , Karner et al. [ 5 ] , and others refined FMA kernels for higher radices, while Bernstein’s tangent FFT [ 6 ] exploited trigonometric identities for global operation count reduction. All of these use the same fundamental factorization identity and share the same singularity. Their factorization uses the identity ax+by=a(x+(b/a)y) , extracting \omega_{i} as the outer multiplier and precomputing the ratio t=\omega_{r}/\omega_{i}=\cot\theta [ 1 , 2 ] . This introduces a singularity at \theta=0 (twiddle W^{0}=1 ), where \omega_{i}=\sin(0)=0 . Standard implementations clamp \omega_{i} to a small epsilon (e.g., 10^{-7} ), which perturbs the twiddle factor and degrades precision—an effect that compounds over the \log_{2}N FFT passes. In this letter, we present two contributions: (1) an alternative factorization that extracts \omega_{r}=\cos\theta instead, first described in [ 3 , 4 ] , which avoids the W^{0} singularity; and (2) a dual-select strategy that combines both factorizations to guarantee |t|\leq 1 for all twiddle factors, eliminating all singularities without epsilon clamping. The practical impact is most significant for half-precision (FP16) FFTs on modern GPU hardware [ 7 ] , where the tighter ratio bound yields a 235\times improvement in the worst-case error bound. II FMA Butterfly Factorizations II-A Standard Butterfly (10 ops) Expanding ( 1 ) into real and imaginary parts: \displaystyle A_{r} \displaystyle=a_{r}+(\omega_{r}b_{r}-\omega_{i}b_{i}),\quad A_{i}=a_{i}+(\omega_{i}b_{r}+\omega_{r}b_{i}), (2) \displaystyle B_{r} \displaystyle=a_{r}-(\omega_{r}b_{r}-\omega_{i}b_{i}),\quad B_{i}=a_{i}-(\omega_{i}b_{r}+\omega_{r}b_{i}). (3) II-B Linzer-Feig Factorization (6 FMA, \div\sin\theta ) Applying ax+by=a(x+(b/a)y) with a=\omega_{i} : \displaystyle s_{1} \displaystyle=b_{i}-\tfrac{\omega_{r}}{\omega_{i}}b_{r},\quad s_{2}=\tfrac{\omega_{r}}{\omega_{i}}b_{r}+b_{i}, (4) \displaystyle A_{r} \displaystyle=a_{r}-s_{1}\omega_{i},\quad A_{i}=a_{i}+s_{2}\omega_{i}, (5) \displaystyle B_{r} \displaystyle=a_{r}+s_{1}\omega_{i},\quad B_{i}=a_{i}-s_{2}\omega_{i}. (6) Each of the six right-hand sides is a single FMA instruction. The precomputed ratio is t_{LF}=\omega_{r}/\omega_{i}=\cot\theta , which is singular at \theta=0 ( W^{0} ) and unbounded as \theta\to 0 . II-C Cosine Factorization (6 FMA, \div\cos\theta ) Applying the same identity with a=\omega_{r} instead: \displaystyle s_{1} \displaystyle=b_{r}-\tfrac{\omega_{i}}{\omega_{r}}b_{i},\quad s_{2}=\tfrac{\omega_{i}}{\omega_{r}}b_{r}+b_{i}, (7) \displaystyle A_{r} \displaystyle=a_{r}+s_{1}\omega_{r},\quad A_{i}=a_{i}+s_{2}\omega_{r}, (8) \displaystyle B_{r} \displaystyle=a_{r}-s_{1}\omega_{r},\quad B_{i}=a_{i}-s_{2}\omega_{r}. (9) The precomputed ratio is t_{B}=\omega_{i}/\omega_{r}=\tan\theta , which is singular at \theta=\pi/2 ( W^{N/4} ). This factorization was first described in [ 3 ] as a method to avoid the W^{0} singularity. However, it introduces a different singularity at W^{N/4} , with |t_{B}|\to\infty as \theta\to\pi/2 . II-D Observation: Complementary Singularities The key observation is that the two factorizations have complementary singularity regions: • Linzer-Feig: |t_{LF}|=|\cot\theta| is small when |\theta| is near \pi/2 (large |\sin\theta| ) and large when |\theta| is near 0 . • Cosine: |t_{B}|=|\tan\theta| is small when |\theta| is near 0 (large |\cos\theta| ) and large when |\theta| is near \pi/2 . At any angle \theta , \min(|\tan\theta|,|\cot\theta|)\leq 1 , with equality at \theta=\pi/4 . This elementary trigonometric identity enables a simple selection rule. III Dual-Select Strategy Algorithm 1: Dual-Select Twiddle Precomputation Input: FFT size N Output: Twiddle table T[k]=(\text{mult},\text{ratio},\text{flag}) for k=0 to N/2-1 do \theta\leftarrow-2\pi k/N ; \omega_{r}\leftarrow\cos\theta ; \omega_{i}\leftarrow\sin\theta if |\omega_{r}|\geq|\omega_{i}| then // cosine path T[k]\leftarrow(\omega_{r},\;\omega_{i}/\omega_{r},\;\textsc{cos}) else // sine path T[k]\leftarrow(\omega_{i},\;\omega_{r}/\omega_{i},\;\textsc{sin}) end if end for For each twiddle factor W^{k} , we select the factorization whose outer multiplier has larger absolute value (Algorithm III ). This guarantees: Theorem 1 . For all twiddle factors W^{k}=e^{-j2\pi k/N} with 0\leq k|\omega_{r}| , we use the sine factorization and store t=\omega_{r}/\omega_{i} with |t|=|\cot\theta|<1 . In both cases, |t|\leq 1 . ∎ Implementation. The selection flag can be encoded in the sign bit of the twiddle table or as an integer flag. The butterfly kernel branches on this flag, executing one of two 6-FMA code paths. Since both paths have identical instruction counts (6 FMAs each), any SIMD divergence on GPU architectures (Apple Metal, CUDA) incurs no throughput penalty—the execution cost is the same regardless of path. Storage overhead : one additional bit per twiddle factor. For N=1024 , this is 64 bytes vs. 4 KB for the twiddle table itself—negligible. IV Error Analysis IV-A Per-Butterfly Error Bound In a single FMA butterfly, the precomputed ratio t appears as a multiplicand in two of the six FMA operations ( 4 ) or ( 7 ). The rounding error of each FMA is bounded by \epsilon_{\text{mach}}|t|\cdot|b| , where \epsilon_{\text{mach}} is the machine epsilon and |b| is the input magnitude. The per-butterfly error scales as: \delta\leq C\cdot|t|\cdot\epsilon_{\text{mach}}\cdot\|b\| (10) for a constant C depending on the butterfly structure. The dual-select strategy ensures |t|\leq 1 , minimizing this bound. IV-B Cumulative Error Over \log_{2}N Passes For a Stockham FFT with m=\log_{2}N passes, each sample participates in m butterfly operations. In the worst case, the cumulative relative error grows as: E\leq(1+|t_{\max}|\cdot\epsilon_{\text{mach}})^{m}-1\approx m\cdot|t_{\max}|\cdot\epsilon_{\text{mach}}. (11) V Experimental Results Table I compares the three strategies for N=1024 ( m=10 passes). TABLE I: Precomputed ratio bounds and error analysis for N=1024 . Strategy |t|_{\max} Sing. FP16 bound Linzer-Feig [ 1 ] ( \div\sin ) 163.0 1 7.95\times 10^{-2} Cosine [ 3 ] ( \div\cos ) >10^{16} 0 ∗ divergent Dual-Select (ours) 1.000 0 \mathbf{4.88\times 10^{-4}} ∗ Near-singular: |\cos\theta|\approx 6\times 10^{-17} at k=N/4 . FP16 bound: per-butterfly, \epsilon_{\text{FP16}}=4.88\times 10^{-4} . TABLE II: Cumulative FP16 error bound over m=10 Stockham passes. Strategy Cumulative bound Improvement Linzer-Feig 1.15 — Dual-Select \mathbf{4.89\times 10^{-3}} \mathbf{235\times} Ratio bound (Table I ). The Linzer-Feig factorization has |t_{\max}|=|\cot(\pi/512)|=163.0 for N=1024 , occurring at k=1 (the smallest nonzero twiddle angle). The cosine factorization has |t|>10^{16} near k=N/4 , where \cos\theta\approx 0 . The dual-select strategy achieves |t_{\max}|=1.0 exactly, at k=N/8 where |\cos\theta|=|\sin\theta|=1/\sqrt{2} . FP16 error (Table II ). Over 10 passes with FP16 machine epsilon \epsilon=4.88\times 10^{-4} , the cumulative error bound ( 11 ) yields 1.15 for Linzer-Feig (rendering the FFT result meaningless) versus 4.89\times 10^{-3} for dual-select—a 235\times improvement. FP32 precision. In float32 ( \epsilon=5.96\times 10^{-8} ), both strategies produce equivalent roundtrip error ( {\sim}10^{-7} relative L2), confirming that the advantage is specific to low-precision arithmetic where the ratio amplification exceeds the precision floor. Path distribution. For N=1024 , exactly 256 of 512 twiddle factors use the cosine path ( |\cos\theta|\geq|\sin\theta| , angles near 0 and \pi ) and 256 use the sine path (angles near \pm\pi/2 ), a 50/50 split. VI Discussion The dual-select strategy has several practical implications: Mixed-precision FFT. Modern GPU architectures (Apple M-series, NVIDIA Tensor Cores) offer 2 \times throughput for FP16 vs. FP32. The primary barrier to FP16 FFTs is precision loss during twiddle multiplication. With |t|\leq 1 guaranteed, the dual-select butterfly is a key enabler for practical FP16 FFTs. Zero overhead. The strategy modifies only the precomputed twiddle table—the butterfly kernel executes 6 FMA instructions regardless of which path is taken. The per-twiddle branch can be eliminated entirely by encoding the operand ordering into the precomputed table entries. Generality. The dual-select principle applies to any radix: for radix- r butterflies with FMA factorization, each twiddle multiplication can independently select the min-ratio path. The proof that \min(|\tan\theta|,|\cot\theta|)\leq 1 is independent of FFT size or radix. VII Conclusion We have shown that the Linzer-Feig and cosine FMA butterfly factorizations have complementary singularities, and that a simple per-twiddle selection rule—choosing whichever yields |\text{ratio}|\leq 1 —eliminates all singularities with zero computational overhead. For FP16 FFTs on modern GPUs, this reduces the worst-case error bound by 235\times for N=1024 , making half-precision FFT a practical option for throughput-critical applications such as real-time radar and neural network inference.