🚀 go-pugleaf

There is in fact a general algorithm to rapidly compute the DFT of a
sequence n points, for any n, odd, even, prime, or other.  This method
is variously known as the "chirp-z transform" or the "fractional
Fourier transform".  It is only about four times more expensive than a
conventional FFT (comparing the cost for n near a power of two).  In
fact this method employs an FFT in a key step.

This technique has a number of other applications, including computing
DFTs of sparse (i.e. mostly zero) sequences, analyzing sequences with
non-integer periodicities, performing high-resolution trigonometric
interpolation, detecting lines in noisy images and detecting signals
with linearly drifting frequencies.

Excuse my immodesty, but a good writeup of this method is the article
"The Fractional Fourier Transform and Applications", by myself and P.
N. Swarztrauber, SIAM Review, Sept. 1991.

David H. Bailey