fonction récursive : comment améliorer le temps de calcul?

bonsoir !!
voila j'ai écris un fonction avec matlab mais le temps de calcul est trés grand
commet je peut améliorer cette fonction pour y remédier ??
merci d'avance ;)
voici le code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

function [tn] = cheby(n,x,N)   a=-(n*(n+1)-(2*x-1)*(x-N-1)-x)/(x*(N-x)); b=((x-1)*(x-N-1))/(x*(N-x)); if (n==0 && x==0) tn=sqrt(1/N); elseif (x==1 && n>=1) tn=(1+(n*(n+1))/(1-N))*cheby(n-1,0,N); elseif (x==0 && n>=1) tn=(-sqrt(((N-n)*(2*n+1))/((N+n)*(2*n-1))))*cheby(n-1,0,N); else if (x>=2 && x<=(N/2))   tn=a*cheby(n,x-1,N)+b*cheby(n,x-2,N);   else tn=cheby(n,(N-1-x),N)/(-1.^n); end end

---

Bonjour,

Déjà tu peux décaler ton calcul de a et b pour le mettre dans la boucle conditionnelle où il sert. Ça ne sert à rien de le calculer si tu ne vas pas l'utiliser. Ensuite, tout dépend du but de ce que tu entreprends :

Si ton but est simplement de connaitre les X premiers termes de ta suite t(n,x,N), alors le mieux est probablement de stocker les résultats dans une matrice en 3 dimensions, de lancer une boucle de manière à que ce chaque terme que tu calcules n'ait besoin que des termes précédemment calculés, et comme ça tu n'as pas besoin d'une fonction récursive, tu fais simplement appel aux résultats précédents.

Si tu as besoin ponctuellement de t(x,y,z) et que tu te fous des résultats intermédiaires, ta méthode est probablement la plus rapide. Si toutefois au long de ton programme tu as besoin des termes dans l'entourage de (x,y,z), il peut être intéressant de stocker ces valeurs intermédiaires afin de les avoir disponibles lors du calcul suivant, et donc d'accélérer grandement le calcul suivant.


Autre chose, je n'ai pas reconnu cette suite que tu veux calculer, mais si c'est un problème courant, tu peux éventuellement chercher sur google s'il n'y aurait pas des simplifications à faire, voire même si elle ne pourrait pas être exprimée sans récurrence.

merci pour votre réponse !!
pour a et b le temps est légèrement amélioré
mais quand x>=30 le calcule devient super lent
la fonction permet de calculer les valeur du polynôme de Chebyshev
elle est obligatoirement récursive .
est ce que la décomposition de cette fonction en plusieurs fonction est meilleur??

Juste un conseil qui ne changera rien au résultat : tu devrais donner un nom plus long à ta fonction car là on a du mal à voir où elle est appelée dans le code (elle se confond avec les variables).

C'est d'ailleurs une habitude à prendre que de donner des noms "parlant" à tes fonctions.

mercii c'est fait !!:ccool:
et pour mon problème :cry:

J'ai du mal à voir le rapport avec les polynômes de Chebyshev. Pourquoi y a-t-il trois variables, à quoi correspondent-elles ?

Toujours est-il qu'apparemment, tu veux calculer tous les termes. Sauvegardes tes résultats dans une matrice T[n,x,N] (remplie de zéros ou NaN au préalable).
Quand tu veux calculer T[X,Y,Z], fais appel à ta fonction cheby, et ne l'appelle de façon récursive que si les termes précédents dont tu as besoin n'ont pas déjà été calculés dans ta matrice T.

Ta fonctions serait alors

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

function T=cheby(n,x,N,T)     if (n==0 && x==0) T(n,x,N)=sqrt(1/N); elseif (x==1 && n>=1) if ~isnan(T(n-1,0,N)) T(n-1,0,N)=(1+(n*(n+1))/(1-N))*T(n-1,0,N); else T=cheby(n-1,0,N,T); T(n-1,0,N)=(1+(n*(n+1))/(1-N))*T(n-1,0,N);   %and so on...

---

EDIT: j'ai supposé que n,x et N étaient entiers.

Par ailleurs, ta définition de t(n,x,N) est la suivante:

t(0,0,N) = f1(N)

t(n>=1,0,N) = f2(n,x,N).t(n-1,0,N)

t(n>=1,1,N) = f3(n,x,N).t(n-1,0,N)

t(n,2<=x<=N/2,N) = f4(n,x,N).t(n,x-1,N) + f5(n,x,N).t(n,x-2,N)

t(n,N-1>=x>N/2,N) = f6(n,x,N)*t(n,N-1-x,N)


Au vu de cet ensemble, si tu parcours les variables dans l'ordre suivant, tu ne devrais jamais avoir de récursivité:

Code:

---

1 2 3 4 5 6 7

T=NaN(nn,xx); for x=0:xx for n=0:nn T=cheby(n,x,N,T); end end

---

merci :ccool:
je vais essayé cette méthode et je vous tiens au courant

Chef, j'm'a trompé dans les indices de T, mais tu devrais pouvoir corriger ça :p