Algorithme de Cooley-Tukey

Implémentation de l'algorithme de Cooley-Tukey calculant en $O(n\log(n))$ la transformée de Fourier discrète d'un signal de taille $2^k$. Utilisé ici pour calculer efficacement le produit de deux polynômes, sous des instances d'une classe Polynomial. Une classe complex_array est implémentée pour faciliter la manipulation des tableaux de type std::complex. On retrouve aussi une méthode de permutation bit inversé d'un coût total de $O(n\log(n))$ pour permettre un algorithme FFT itératif "in-place".

Théorie

[TODO]

Source: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, Cambridge (Mass.)