Discussion :

[pgz]

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?

[shaku]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Maxence HUBICHE]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Le pire, c'est que ça marche



Sinon, tu te rapproches dangereusement de la solution !

[pgz]

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...

[Maxence HUBICHE]

@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)

[shaku]

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

[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?

@Shaku.

Il faut que tu ilitialises quelque chose avant la boucle.

[shaku]

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

[Maxence HUBICHE]

@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

[pgz]

@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 = ...

[shaku]

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 .

[Maxence HUBICHE]

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 !
et... il ne descend pas sous 0.0015

[shaku]

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 .

[pgz]

@Shaku.

En voilà un simple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[shaku]

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

[Maxence HUBICHE]

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é !

[shaku]

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 ?

[pgz]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

[shaku]

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 ?

[Maxence HUBICHE]

@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