Software manipulations to speed up a real-valued fast Fourier transform algorithm

It is described how a real-valued fast Fourier transform (RFFT) algorithm can be converted quite easily into a computer program in which loops, evaluation of subscripts, exchange of data, and logical operations are completely avoided. The resulting program runs considerably faster than the original algorithm. The actual saving of execution time depends upon both the computer system and the length of the RFFT. In the majority of the investigated cases the execution time was reduced by a factor between 1.8 and 5. The described technique can be recommended especially for critical real-time tasks and for applications requiring a huge amount of RFFT evaluations. Other algorithms as for example the complex-valued FFT, the inverse RFFT or correlation algorithms can be treated in a similar way.