Voici le code d'une FFT raisonnablement rapide, raisonnablement petite (le code tient dans un fichier) et raisonnablement pas chiante au niveau de la license (c'est du bsd). Paradoxalement, ce n'était pas facile d'en trouver une qui réponde à ces contraintes.

Que s'appelorio PFFFT.