Discussion :

[membreComplexe12]

Bonjour tous,

j'ai une petite question :

qu'es ce que ça fait si on utilise un algorithme "fft" avec un nombre de points qui n'est pas un multiple de 2 ?

J'ai testé et apparemment ça ne change pas grand chose, j'aimerai comprendre alors pourquoi il faut respecter ceci ?

merci pour votre aide

[shaiHulud]

Bonjour,

En lisant la doc de fft en diagonale, je n'ai pas l'impression qu'il y soit fait mention d'une contrainte de type n=2^k. D'ou tiens-tu qu'il faille "respecter ceci"

[membreComplexe12]

merci d'avoir pris le temps de répondre,

en fait je ne tire pas cette info de la doc de matlab mais de cours que j'ai lu sur le net, ils disent qu'une FFT c'est comme une transformée de fourier discrete mais on prend un nombre de point qui est multiple de 2.

du coup j'ai essayé avec matlab de mettre quelque chose non multiple de deux et ça fonctionne mais je ne sais pas quoi dire sur le résultat :

=> est il correct ? dans quelle mesure ?

[shaiHulud]

from wiki fft

The most well-known use of the Cooley–Tukey algorithm is to divide the transform into two pieces of size N/2 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 is recursive, most traditional implementations rearrange the algorithm to avoid explicit recursion. Also, because the Cooley–Tukey algorithm breaks the DFT into smaller DFTs, it can be combined arbitrarily with any other algorithm for the DFT, such as those described below.

from doc fft

The FFT functions (fft, fft2, fftn, ifft, ifft2, ifftn) are based on a library called FFTW [3],[4]. To compute an N-point DFT when N is composite (that is, when N = N1N2), the FFTW library decomposes the problem using the Cooley-Tukey algorithm [1], which first computes N1 transforms of size N2, and then computes N2 transforms of size N1. The decomposition is applied recursively to both the N1- and N2-point DFTs until the problem can be solved using one of several machine-generated fixed-size "codelets." The codelets in turn use several algorithms in combination, including a variation of Cooley-Tukey [5], a prime factor algorithm [6], and a split-radix algorithm [2]. The particular factorization of N is chosen heuristically.

When N is a prime number, the FFTW library first decomposes an N-point problem into three (N – 1)-point problems using Rader's algorithm [7]. It then uses the Cooley-Tukey decomposition described above to compute the (N – 1)-point DFTs.

For most N, real-input DFTs require roughly half the computation time of complex-input DFTs. However, when N has large prime factors, there is little or no speed difference.

The execution time for fft depends on the length of the transform. It is fastest for powers of two. It is almost as fast for lengths that have only small prime factors. It is typically several times slower for lengths that are prime or which have large prime factors.

Donc si j'ai bien compris, plutôt qu'une base 2, fft() utilise les bases donnés par la décomposition de n en facteur premiers.

[membreComplexe12]

ouahou, ça à l'air compliqué un peu tout ça.

VV3D en fait c'est le contraire : si on a un nombre de point qui est un nombre premier alors ça va etre lent et si c'est une puissance de 2 ça va etre rapide.

ce que j'ai compris c'est qu'en fait si je prends un nb de points "2^n" alors l'algo sera plus rapide mais si je ne respect pas ceci alors ça fonctionnera aussi mais ça sera seulement plus lent

merci pour ton aide, je crois que j'ai compris à présent