fonction récursive un peu lente

En récursivité tu dis : F(n) = F(n-1) + F(n-2),
puis avec la même relation tu évalues F(n-1) ...

En itératif tu dis :
F(0) = 0
F(1) = 1
F(2) = F(0) + F(1)
Etc..
jusqu'à F(n).

Tu ne vois pas la différence?

non je ne vois pas du tout comment mettre ça dans une boucle

Code:

---

1 2 3 4 5 6 7

For i = 0 To n x = i y = i + 1 z = x + y Next i   fibonacci = z

---

ça marche pas

Bon, allez...
y'en a marre des récursif et itératifs et tout le bazard !
Le même, mais en une seule ligne !
Et paf !

Code:

---

1 2 3

Function fibo(n As Long) As Long fibo = 1 / Sqr(5) * (((1 + Sqr(5)) / 2) ^ n - ((1 - Sqr(5)) / 2) ^ n) End Function

---

:lol:
:lol:

Le pire, c'est que ça marche ;)



Sinon, tu te rapproches dangereusement de la solution !

Ca ne marche pas mais cette fois tu t'approches.
Exécutes ton code et suit le pas à pas, tu vas comprendre où le bât blesse et améliorer...

@pgz !
J'ai du mal à départager ta fastFibo et ma dernière fibo en terme de rapidité de traitement...
TU peux me donner des stats sur ton poste ?
Moi, même en utilisant GetTickCount, sur mon PC, les deux renvoient 0 pour une F(n) où n=20
La récursive du départ ne me renvoyant que 16
(ben oui, il va vite mon P, et alors)

pgz t'es certain que je peux mettre mes 3 variables dans une boucle et rien mettre en dehors de la boucle ?

@Maxence.
Pour mesurer je calcule 10 000 fois F(n). Je mesure ausi avec GetTickCount& et je divise par 10 000.

Pour FastFibo, j'obtiens 15 µs ,
Pour ma FiboIter, j'obtiens 5 µs.

Tu veux que je mesure ta formule?

@Shaku.

Il faut que tu ilitialises quelque chose avant la boucle.

je précise que je n'ai vu que des boucles for basiques , et avec cette architecture de boucle je vois pas comment avec 3 variables, tomber sur le bon résultat

Citation:

---

Envoyé par pgz

@Maxence.
Pour mesurer je calcule 10 000 fois F(n). Je mesure ausi avec GetTickCount& et je divise par 10 000.

Pour FastFibo, j'obtiens 15 µs ,
Pour ma FiboIter, j'obtiens 5 µs.

Tu veux que je mesure ta formule?

---

Ouaip !
pour voir ...
à priori, la formule en 1 ligne va environ 3 fois plus vite que la fastFibo

@Maxence.

J'ai oublié de préciser : je calcule F(30).

Avec ta formule : 1,6 µs.

Ma machine est lambda. On retombe sur les limite de GetTickCount, on dirait que l'incrément de mesure est 16 ms.

ET 16 ms / 10 000 = ...

là j'ai vraiment aucune idée sur cette question , je ne sais pas quoi ni comment initialisé quelque chose dans ce cas , je ne sais pas quand ma boucle doit commencer , où mettre une initialisation...

bref je ne comprends rien donc si tu veux mettre un code tout fait tu peux j'abandonne .

Citation:

---

procedure fibonacci (n : entier non négatif)

si n = 0 alors y := 0

sinon
début

x := 0
y := 1

pour i := 1 à n−1

début

z := x + y
x := y
y := z

fin
fin

---

y est le n-ième nombre de Fibonacci

@PGZ
Voici les stats que j'obtiens pour F(40) en 10 000 itérations
FIBO : 0,0015
FASTFIBO : 0,0078
Soit 5 fois plus rapide ! :aie:
et... il ne descend pas sous 0.0015 :?

ah ben vous m'aviez pas dit que je devais mettre des alternatives j'en savais rien moi j'aurais pû chercher longtemps!!!

merci bien maxence je vais essayer de traduire ça , et merci aussi pgz .

@Shaku.

En voilà un simple

Code:

---

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

Function fctFiboIter(ByVal n As Integer) As Long Dim FnMoins1 As Long, FnMoins2 As Long, i As Integer   FnMoins2 = 0 FnMoins1 = 1 fctFiboIter = n   For i = 2 To n fctFiboIter = FnMoins1 + FnMoins2 FnMoins2 = FnMoins1 FnMoins1 = fctFiboIter Next i   End Function

---

@Maxence

Mesure avec F(30), 100 000 calculs entre deux mesures de temps:
FastFibo : 13 µs
FiboIter (ci-dessus) : 3,8 µs
Ta fonction : 1,7 µs

En absolu, faut être prudent mais en relatif, c'est net.

merci bcp pgz :? , je vais sérieusement revoir mon étude des boucles car là j'ai du soucis à me faire , encore merci à vous 2 .

J'ai voulu faire mon malade mental ...

500k itérations F(40)
FastFibo= 0,00471
Fibo = 0,00103

Après, je teste à 1000k itérations F(40)
FastFibo= 0,004742
Fibo= 0,000952

Quelle que soit la manière, c'est super rapide cette formule ! étonnant de rapidité !
Entre 4 et 5 fois plus rapide !
Je suis soufflé !

juste un truc pgz , dans mes cours après le next ya tjs une instruction de retour du genre fonction = ...

pq tu n'en mets pas toi ?

Parce que là, je l'ai fait avant. Pour toi, il aurrait été plus clair de faire

Code:

---

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

Function fctFiboIter(ByVal n As Integer) As Long Dim FnMoins1 As Long, FnMoins2 As Long, i As Integer, A as long   FnMoins2 = 0 FnMoins1 = 1 A = n   For i = 2 To n A = FnMoins1 + FnMoins2 FnMoins2 = FnMoins1 FnMoins1 = A Next i fctFiboIter = A End Function

---

Mais ce n'est pas mieux, non?

ok je vois , j'ai excel 2003 , hier tu m'as montré grâce à une astuce avec cette ligne : Debug.Print "appel n = " & n , comment voir l'execution pas à pas .

J'aimerais aussi voir cette éxécution avec la boucle , je dois mettre cette ligne où ? Je ne peux pas voir l'execution pas à pas autrement que pas cette ligne ?

@PGZ !
Par contre, fastFibo est plus rapide sur les petites valeurs de n !!

@SHAKU
Regardes dans le menu Débogage : Tu peux mettre un point d'arrêt à un endroit (F9) et avancer pas à pas (F8)
Tu as aussi, dans le menu affichage une fenêtre intéressante : la fenêtre des variables locales :)