Modified ffts for fused multiply-add architectures

We introduce fast Fourier transform algorithms (FFTs) designed for fused multiply-add architectures. We show how to compute a complex discrete Fourier transform (DFT) of length n = 2mwith8/3nm-16/9n+ 2/9(-1)mreal multiply-adds. For real input, this algorithm uses4/3nm– 17/9n+3-1/9(-1)mreal multiply-adds. We also describe efficient multidimensional FFTs. These algorithms can be used to compute the DFT of an nx n array of complex data using 14/3n2m- 4/3jn2(-1)m+16/9 real multiply-adds. For each problem studied, the number of multiply-adds that our algorithms use is a record upper bound for the number required. © 1993 American Mathematical Society.