Supercomputer-style FFT library for Apple G4

transform (FFT) and associated convolution/correlation routines. Though arbitrary signal lengths (i.e. all powers of 2) are handled, our design emphasis is on very long signals (length N ≥ 2 16 and on into the millions), for which cache considerations are paramount. The core of the library is a particular variant of full-complex FFT that for signal length N = 2 10 executes at 1.15 gigaflops (500 MHz G4). This cache-friendly, core FFT plays a dominant role in the long-signal cases such as two-dimensional FFT and convolution. More important perhaps than the core performance benchmark is the manner in which one can sift through the myriad prevailing (and new) FFT frameworks, to arrive at a suitable such framework for the Velocity Engine. Presumably these means of adapting algorithms to the Velocity Engine architecture and features will carry over to other engineering problems