Optimum Complexity FFT Algorithms for RISC Processors

Modern RISC processors provide a special instruction -- the fused multiplyadd (FMA) instruction \Sigmaa \Sigma b \Theta c -- to perform both a multiplication and an addition operation at the same time. In this paper newly developed radix-2, radix-4, and split-radix FFT algorithms that optimally take advantage of this powerful instruction are presented. All floating-point operations of these algorithms are executed as FMA instructions. If a processor is provided with FMA instructions, the radix-2 FFT algorithm introduced has the lowest complexity of all Cooley-Tukey radix-2 algorithms. The new radix-4 algorithm requires 15 % fewer floating-point operations and 10 % fewer memory accesses than conventional Cooley-Tukey radix-4 algorithms. In general, the advantages of the FFT algorithms presented in this paper are their low complexity, their high efficiency, and their striking simplicity. Contents 1 Introduction 4 2 Arithmetic Complexity 6 2.1 Multiply-Add Complexity . . . . . . . . ..