Cooley-Tukey algorithm speed

After the last block has been transformed, the data has been subjected to I passes of a Cooley-Tukey algorithm. All that remains to complete the transform are the final M-I passes. During these passes, the data points for the 2-by-2 transforms are always in different blocks of the array. Thus, dual windows are necessary. Furthermore, subsequent passes act on different blocks of data, and an approach in which multiple passes are performed for discrete blocks of data (as in the internal transforms) is impossible. Consequently, the final passes are characterized by extensive re-mapping each block in the array is re-mapped once during each pass. To make matters worse, two windows are in use and the block size is reduced to half the size of the window used for the internal transform. As in the bit reversal routine, the speed-limiting step, therefore, is the re-map operation. 

In the early days, this Fourier transformation was a time-consuming, expensive and difficult task due to limited computer speed and capacity. However, with the advent of the fast Fourier transform algorithm of Cooley and Tukey 6) and the improvement in computers, this problem has been resolved so that real time spectra can be obtained with the transformation time of the order of fractions of seconds. 

---