BIT REVERSAL ON UNIPROCESSORS

Many versions of the fast Fourier transform require a reordering of ei ther the input or the output data that corresponds to reversing the or der of the bits in the array index. There has been a surprisingly larg e number of papers on this subject in the recent literature. This pape r collects 30 methods for bit reversing an array. Each method was reco ded into a uniform style in Fortran and its performance measured on se veral different machines, each with a different memory system. This pa per includes a description of how the memories of the machines operate to motivate two new algorithms that perform substantially better than the others.