around 1805 (and subsequently rediscovered several times in limited forms).

The best known use of the Cooley-Tukey algorithm is to divide the transform into two pieces of size at each step, and is therefore limited to power-of-two sizes, but any factorization can be used in general (as was known to both Gauss and Cooley/Tukey). These are called the radix-2 and mixed-radix cases, respectively (and other variants such as the split-radix FFT have their own names as well). Although the basic idea