Separar la suma per parells i imparellls Recordem: `F(n)=1/N\sum_{k=0}^(N-1) f(k)e^((-i2pikn)/N)` S'ha descobert que espoden reduir molt el nombre de càlculs separant l'expressió anterior en suma de termes parells i els imparells: `F(n)=1/N[\sum_{k=0}^(N/2-1) f(2k)e^((-i2pi2kn)/N)+\sum_{k=0}^(N/2-1) f(2k+1)e^((-i2pi(2k+1)n)/N)]` `F(n)=1/N[\sum_{k=0}^(N/2-1) f(2k)e^((-i2pi2kn)/N)+\sum_{k=0}^(N/2-1) f(2k+1)e^((-i2pi2kn)/N)·e^((-i2pin)/N)]` `F(n)=1/N[\sum_{k=0}^(N/2-1) f(2k)e^((-i2pi2kn)/N)+e^((-i2pin)/N)·\sum_{k=0}^(N/2-1) f(2k+1)e^((-i2pi2kn)/N)]` `F(n)=1/N[\sum_{k=0}^(N/2-1) f(2k)e^((-i2pikn)/(N/2))+e^((-i2pin)/N)·\sum_{k=0}^(N/2-1) f(2k+1)e^((-i2pikn)/(N/2))]` Si ens fixem en l'última expressió veiem que hem convertit el càlcul dels coeficients de Fourier de `N` dades en el càlcul de dues sèries de Fourier, una pels valos de `f(k)` parells i una altra pels imparells. I això quina avantatge té. Suposem que la nostra funció té `16` dades, que pel que hem dit abans serien unes `16^2 = 256` multiplicacions. Si ho convertim en el càlcul de dues sèries de `8` dades, per cadascuna d'elles necesitarem `8^2 = 64` multiplicacions. Com tenim `2` sèries, caldrà fer el doble `64*2 = 128`. D'alguna manera hem pasat d'haver de fer `256` a `128` operacions. Si sabem com fer-ho, sembla que la reducció d'operacions és considerable, però `->` Si a cada funció de `8` dades fem el mateix , és a dir, dividir per dues sèries amb els parells i imparells de les dues noves sèries caldrà fer `4` transformades de Fourier amb `4` dades cadascuna. O sigui per cadascuna d'elles caldrà fer `4*4 = 16` multiplicaions. Com tenim `4` series caldrà fer `16*4 = 64` operacions. Què passsa aquí? Hem passat de necessitar `256` operacions a `64`. I si arrivem a fer `8` transformades de Fourier de `2` dades cadascuna, llavors passariem a haver de fer `2^2*8 = 32` operacions. Aquesta idea és la base de l'FFT, primer que el nombre de dades, `N` sigui una potència de `2` i calcular `log_2^N` (`16` dades hem dividit per `2`, `4=log_2^16` vegades) transformades de Fourier de `2` dades cadascuna. Es passa de `N^2` Càlculs a `N·log_2^N`. Així si partim de `1024` dades passem de l'ordre de `1024^2 = 1048576` i fent servir l'FFT, per obtenir el mateix, `1024·log_2^1024=1024·10=10240` on s'aconsegueix una millora de `100` vegades menys.