Automating the design of prime length FFT programs

The automatic design of prime-length fast Fourier transforms (FFTs) based on S. Winograd´s (1980) theory is described. A program is described that generates code for FFTs so that longer prime length FFTs that were formerly practical to design are now easily generated. For those prime lengths (⩽19) for which FFTs already exist, the program produces equally efficient FFTs. The new FFT programs generated do not have the minimum number of multiplications but do have a more practical balance between additions and multiplications