Bordeaux-FFT is a fast, pure-Lisp implementation of Fast Fourier Transforms.

Bordeaux-FFT operates on one-dimensional arrays of complex numbers. It caches coefficients and scratch buffers, so if you are doing consecutive FFTs on the same size array, you get a nice boost in speed.

More details and a link to the source can be found in the fine manual.

Mathematics algorithm