vitesse d'un algorithme FFT

[invitec35bc9ea]

bonjour,
qqun saut-il combien de cycles machine prends un algorithme FFT pour s'executer (en fct de la frequence du processeur et du nbr d'echantillons)?
merci
-----

[jiherve]

Bonsoir
farfouille à partir de là:http://www.fftw.org/
JR

[polo974]

c'est totalement indépendant de la fréquence du processeur... par contre ça dépends du processeur...

c'est de l'algo, ça, donc plus info qu'électronique...

Par contre, de mémoire, il a moyen de presque diviser par 2 le nombre de "papillons" à calculer si les données en entrée sont réelles et non complexes.

[invitec35bc9ea]

bonsoir,
j'ai fini par trouver: ça fait Nlog2(N) cycles d'horloge donc ça depend de la frequence du proc

[A voir en vidéo sur Futura]

[jiherve]

Bonsoir
Toute durée d'exécution d'un algorithme quel qu'il soit dépend de la fréquence du processeur, cela dépend aussi bien sur de l'architecture du processeur et des caractéristiques des périphériques, par contre il existe certaines lois :
quelle que soit l'efficacité d'un hardware alors il existera un software qui la réduira à néant.
Quelle que soit la taille de la mémoire disponible alors il y aura un software pour la saturer.
Je vis ça tous les jours depuis 35 ans!
JR

[polo974]

bonjour,
qqun saut-il combien de cycles machine prends un algorithme FFT pour s'executer (en fct de la frequence du processeur et du nbr d'echantillons)?
merci

bonsoir,
j'ai fini par trouver: ça fait Nlog2(N) cycles d'horloge donc ça depend de la frequence du proc

Tu le dis 2 fois (cycles) et tu te contredis ! ! !Que l'horloge soit à 32768Hz ou à 3GHz, c'est toujours autant de cycles (N*log₂(N)), par contre le temps d'exécution n'est pas le même!

En plus, les N*log₂(N) sont le nombre de papillons qui représentent quelques multiplications et additions.

Et si les échantillons d'entrés sont réels (partie imaginaire nulle), on peut réduire à (N/2)*(1+log₂(N)) (environ et de mémoire), ce qui représente un gain non négligeable.