A Common Lisp library to do Fast Fourier Transform on a multi-dimensional array of numbers. See Bordeaux-FFT for a faster implementation for one-dimensional arrays.

This library is by Patrick Stein.

The array can be any number of dimensions, but each dimension must be a power-of-two in size.

ASDF-install package (obsolete) http://nklein.com/wp-content/uploads/2011/03/fft_1.4.2011.03.24.tar.gz

Here is a simple example on a two-dimensional input buffer.

(require :asdf)
(asdf:operate 'asdf:load-op 'fft)

(defparameter *buf* #2A((1 2 3 4)(5 6 7 8)))

(let ((transformed (fft:fft *buf*)))
    (fft:ifft transformed))

Here is an example using the a parallelized version that uses pcall which, in turn, uses Bordeaux-Threads:

(require :asdf)
(asdf:operate 'asdf:load-op 'pfft)

(defparameter *buf* #2A((1 2 3 4)(5 6 7 8)))

(let ((transformed (pfft:pfft *buf*)))
    (pfft:pifft transformed))

For a more complete description, see the home page.

Unfortunately, I messed up by capitalizing the page name here on the Cliki. As such, to install it with ASDF-Install, you need to do this:

(asdf-install:install '|FFT|)