Rapidly "Bit-reversing" data for the past Fourier transform

In most variations of the Fast Fourier Transforms, the data to be transformed must be permuted in a peculiar way either before or after the trigonometric calculations. On typical computer implementations, this adds from 10% to 25% to the running time. Besides the actual data exchanges, much time is consumed computing which data to exchange. The technique described here permits this permutation to be performed on any computer, without special hardware, with very little time for the determination of the exchange indices, and with very little additional storage. It is most useful when the number of points to be permuted is fixed.