Optimisation Suite de Fibonacci

Citation:

---

Envoyé par SimonDecoline

La récursivité permet de faire la même chose que les boucles et presque toujours aussi efficacement, si on ne la code pas n'importe comment. Par exemple, pour fibonacci :

Code:

---

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

#include <stdio.h> #include <stdint.h>   uint64_t fib_aux(uint64_t n, uint64_t u, uint64_t v) { return n == 0 ? v : fib_aux(n-1, u+v, u); }   uint64_t fib(uint64_t n) { return fib_aux(n, 1, 0); }   int main() { printf("%llu\n", fib(93)); return 0; }

---

---

Je ne sais pas quoi répondre.

Tu n'utilises pas la récursivité pour calculer fib(n-1) + fib(n-2) ce qui rendrait la fonction C identique à la définition mathématique mais donnerait un truc complètement exponentiel ; tu utilises la récursivité pour remplacer la boucle for (i=0; i < n; i++) { additionner et décaler les élément }. Oui, c'est effectivement ce que tu dis quand tu parles de "remplacer les boucles" mais tu détournes radicalement le but de la récursivité !!!
La récursivité a été créée pour simplifier une tâche complexe. Au lieu de calculer n, je calcule un m inférieur et quand j'ai finit ce calcul, j'intègre le résultat au calcul de n. Et si le calcul de "m" est encore trop complexe, alors rebelote.
C'est ce principe qui permet de montrer le calcul de la factorielle (pour calculer 10 il faut commencer par calculer 9), le calcul de fibonacci (pour calculer 10 il faut d'abord calculer 9 et 8), que j'ai utilisé pour résoudre le jeu "le compte est bon" (pour trouver 123 avec 1, 2, 3, 4, 5 et 6 je regarde si je peux trouver 123 avec 3, 3, 4, 5 et 6). Y recourir ça amène très souvent le mal (comme l'a dit Stellar7) mais on ne peut parfois pas faire autrement. Et même parfois quand on ne peut pas faire autrement, on ne peut pas non plus faire avec (suffit de regarder le code de la fonction Ackerman dont j'ai déjà parlé).
Mais même si la récursivité le permet, jamais elle n'a été créée dans le but de remplacer une simple boucle !!! Si on peut le faire avec une récursivité qui remplace la boucle alors autant le faire tout simplement avec la boucle (cf code de droggo) Ce sera plus simple à écrire et plus simple à lire

Ceci dit, c'était un bel exercice de style :applo:

Citation:

---

Envoyé par Sve@r

Oui, c'est effectivement ce que tu dis quand tu parles de "remplacer les boucles" mais tu détournes radicalement le but de la récursivité !!!

---

Non :mrgreen: c'est le principe de la récursion terminale dont moi et @Stellar7 parlent avant :mrgreen: - ceci permet de ne plus avoir de débordements de pile.

Parce que justement on calcule en même temps et ainsi, le compilateur/ interpréteur peut optimiser (parce qu'il n'a plus besoin des appels précédents).

Mais je me demande si le compilateur C/ C++ le fait automatiquement :koi: mais d'après les résultats de @SimonDecoline, il semble le faire.

Citation:

---

Envoyé par Sve@r

...
La récursivité a été créée pour simplifier une tâche complexe.
...
Mais même si la récursivité le permet, jamais elle n'a été créée dans le but de remplacer une simple boucle !!! Si on peut le faire avec une récursivité qui remplace la boucle alors autant le faire tout simplement avec la boucle (cf code de droggo) Ce sera plus simple à écrire et plus simple à lire

---

Mais non, pas du tout. La récursivité c'est juste une fonction qui s'appelle elle-même et ça sert à calculer (cf lambda-calcul, Godel, Turing, Church & co). La façon dont on l'utilise c'est de l'algorithmique. La notion de récursivité et la notion de boucle sont équivalentes et d'ailleurs certains langages de programmation n'ont pas de boucle et font tout avec de la récursivité.

Citation:

---

Envoyé par foetus

Mais je me demande si le compilateur C/ C++ le fait automatiquement :koi: mais d'après les résultats de @SimonDecoline, il semble le faire.

---

Je ne connais pas bien les normes C/C++ mais je crois que le TCO n'est pas imposé. D'après mes souvenirs, il fallait demander -O1 ou plus pour que GCC optimise mais, en refaisant le test ici, on dirait bien que les dernières versions optimisent tout le temps.

Une dernière remarque : pour implémenter la "vraie définition" de fibonacci avec des boucles, il faudrait faire quelque chose comme ça :

Code:

---

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

#include <stack>   uint64_t fib(uint64_t n) { uint64_t r = 0; std::stack<uint64_t> s; s.push(n); while (not s.empty()) { uint64_t h = s.top(); s.pop(); if (h < 2) { r += h; } else { s.push(h-2); s.push(h-1); } } return r; }

---

NB : c'est du C++, car je me sentais pas trop de recoder une stack en C...

Citation:

---

Envoyé par SimonDecoline

Une dernière remarque : pour implémenter la "vraie définition" de fibonacci avec des boucles, il faudrait faire quelque chose comme ça

---

Là c'est une simulation de la récursivité au travers d'une pile. Plutôt que d'empiler et dépiler le contexte d'appel de la fonction, tu empiles et dépiles juste le calcul en cours. Effectivement c'est mieux (j'ai fait un truc analogue un jour où j'avais besoin d'une grosse récursivité en Python alors que la limite de sa profondeur de récursion est fixée à 1000).

Toutefois j'aime pas quand on dit "vraie définition". Parce que ça sous entend qu'il y en a une fausse.
Fibonacci c'est une suite définie mathématiquement d'une certaine façon. Il se trouve qu'il existe un algorithme qui, à partir de boucles et d'incréments successifs, donne un résultat identique à celui que donne Fibonacci. Comme dirait M. Spock, deux choses identiques à une 3° sont alors identiques entre elles. Si l'algorithme que droggo a codé (et que je vais considérer comme l'algo de base même si v0 ne sert à rien) donne pour n la valeur que donne U(n) (U suite de Fibonacci), alors cet algorithme implémente Fibonacci. Même s'il l'implémente par une autre façon que celle exprimée par la définition mathématique.
Sinon ce serait comme dire que 5*n n'implémente pas la vraie définition de la multiplication (suite d'addition) et donc qu'il faudrait écrire à la place s=0; for (i=0; i < n; i++) s+=5...

Citation:

---

Envoyé par SimonDecoline

car je me sentais pas trop de recoder une stack en C...

---

Hé oui, je te comprends. Donc pour ton plaisir, voici Fibonacci sans boucle, sans récursivité, sans stack. Juste une belle et élégante formulation qui, bien entendu, n'a aucun rapport avec la "vraie" définition mais qui, bien entendu, donne quand-même le "vrai" résultat :mrgreen:

Code:

---

1 2 3 4 5

#include <math.h> unsigned long fib(unsigned short n) { double k=2.23606797749979; // Racine carrée de 5 return (pow((1+k) / 2, n) - pow((1-k) / 2, n)) / k; }

---

A compiler avec -lm pour inclure la librairie mathématique (ou alors il faut aussi implémenter la puissance entière d'un flottant).

Citation:

---

Envoyé par Sve@r

Toutefois j'aime pas quand on dit "vraie définition". Parce que ça sous entend qu'il y en a une fausse.
Fibonacci c'est une suite définie mathématiquement d'une certaine façon.
...

---

Ben justement, c'est toi qui disais que l'algo récursif terminal ne correspondait pas à "la définition mathématique". Sauf que fibonacci peut très bien être définie mathématiquement de plusieurs façons : en partant de n ou en partant de 0.

Citation:

---

Envoyé par Sve@r

voici Fibonacci sans boucle, sans récursivité, sans stack. Juste une belle et élégante formulation qui, bien entendu, n'a aucun rapport avec la "vraie" définition mais qui, bien entendu, donne quand-même le "vrai" résultat :mrgreen:...

---

Oui merci, le calcul de fibonacci à partir du nombre d'or, c'est connu depuis des siècles. C'est effectivement très élégant dans un monde mathématique à précision infini mais dans notre bas monde informatique à précision finie ton algo ne fonctionne pas. Par exemple, pour 93, tu obtiendras quelque chose comme 12200160415121913856 alors que la vraie valeur est 12200160415121876738.

Hello, tu as utilisé une commande Linux pour obtenir le temps de calcul ou une fonction dans le programme ? Moi j'ai fait ceci :

Code:

---

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

clock_t start, end; double total_time;   start = clock();   [...]   int fibonacci_number = calcul_fibonacci(i);   end = clock();   total_time = (end - start) / CLOCKS_PER_SEC;   printf("Temps : %.2f\n", total_time);

---

Mais c'est assez laid et ça ne donne une simple précision à a seconde...

Citation:

---

Envoyé par SimonDecoline

[...]

Code:

---

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

#include <stdio.h> #include <stdint.h>   uint64_t fib_aux(uint64_t n, uint64_t u, uint64_t v) { return n == 0 ? v : fib_aux(n-1, u+v, u); }   uint64_t fib(uint64_t n) { return fib_aux(n, 1, 0); }   int main() { printf("%llu\n", fib(93)); return 0; }

---

---

Il est intéressant ton code, mais je ne le comprends pas très bien...

Citation:

---

Envoyé par SimonDecoline

Et au passage, ça ne sert à rien d'aller au delà de 93 car les résultats ne tiennent plus sur 64 bits et sont donc faux.

---

Merci pour l'indication.


Sinon pour le reste je ne comprends pas trop ce que vous dites, mais j'apprends quand-même deux/trois trucs au passage :mrgreen:

Bonjour,

Pour les prises de temps, par simplicité, j'utilise la bibliothèque Qt, en gros à quelques ms près.

Mais dans les cas ou la précision est vraiment, j'utilise un peu de code assembleur, ce qui permet d'accéder au nombre de cycles du processeur.
Bien entendu, ça reste approximatif, en raison du multi-tâches de Windows, mais c'est tout de même plus précis. :)

Citation:

---

Envoyé par .....1.....

Hello, tu as utilisé une commande Linux pour obtenir le temps de calcul ou une fonction dans le programme ? Moi j'ai fait ceci :[code]clock_t start, end;
Mais c'est assez laid et ça ne donne une simple précision à a seconde...

---

Tu peux utiliser la commande time de Linux (commande shell à placer devant le programme qu'on veut mesurer ie time ./fibonacci (sous-entendu que "fibonacci" est le nom de ton exec). Mais le souci c'est qu'entre le récursif et l'itératif il y aura tellement de différence que l'écart ne veut rien dire. Un peu comme si tu comparais le poids d'une souris et d'un humain (on sait très bien qui est le plus lourd mais de combien exactement tout le monde s'en bat le steak).

Citation:

---

Envoyé par .....1.....

Il est intéressant ton code, mais je ne le comprends pas très bien...

---

Il utilise la récursivité non pas pour simplifier le calcul de Fibonacci (remplacer fib(7) par fib(6) + fib(5)) mais pour remplacer la boucle de droggo. Par exemple pour calculer Fibonacci(10) il faut boucler 10 fois et cumuler 10 fois un compteur. Ben là, il cumule le compteur pour 1 puis passe ce compteur à la récursivité suivante qui va alors le cumuler pour 2 et etc etc jusqu'à 10.

Bonjour,

Décidément, cette discussion me porte la poisse :

j'ai fait ça il y a si longtemps, et avec plusieurs langages, que dans mes archives je dispose de nombreuses versions, qui, à ma grande honte, ne sont pas toutes correctes !

C'est le cas de celle que j'ai postée : en dehors du fameux v0, qui était inutile, il y a un problème sur le calcul :
ci-dessous en rouge la ligne fautive, et en vert la correction faite.

Code:

---

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

quint32 fiboIter(quint32 n) { quint32 u = 1, v = 1, u0, v0; //for (quint32 i=2; i<=n; ++i) for (quint32 i=2; i<n; ++i) { u0 = u; u = u0 + v; v = u0; } return u; }

---

Voilà, cette fois c'est ok.

:)

Citation:

---

Envoyé par droggo

Voilà, cette fois c'est ok.

---

Pas tout à fait... f(0) doit retourner 0 mais ta fonction retourne 1 (https://fr.wikipedia.org/wiki/Suite_de_Fibonacci) .

Bonjour,

Citation:

---

Envoyé par SimonDecoline

Pas tout à fait... f(0) doit retourner 0 mais ta fonction retourne 1 (https://fr.wikipedia.org/wiki/Suite_de_Fibonacci) .

---

Oui, je sais.

MAIS je ne me suis jamais préoccupé de calculer le résultat pour 0, 1 ou 2. :)

Mais si tu y tiens :

Code:

---

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

quint32 fiboIter(quint32 n) { if (n == 0) return 0; if (n <= 2) return 1; quint32 u = 1, v = 1, u0, v0; for (quint32 i=2; i<n; ++i) { u0 = u; u = u0 + v; v = u0; } return u; }

---

On pourrait également étendre pour des valeurs négatives ... :)

Citation:

---

Envoyé par droggo

Décidément, cette discussion me porte la poisse :

---

Pourquoi ? t'aimes pas que je prenne ton code comme référence de base ? Je pensais que ça te ferait plaisir (bon ok il y a v0 mais ça va, une variable inutile c'est pas la cata quoi).

Citation:

---

Envoyé par droggo

Code:

---

1 2	if (n == 0) return 0; if (n <= 2) return 1;

---

---

if (n <=2) return n ?1 :0 8-)

Citation:

---

Envoyé par droggo

...

---

Tu as déjà vu 1 code de Fibonacci itératif basé sur 1 liste (a, b) * :koi: parce que comparer au tien, il n'y a pas 2 tests, seulement 1 variable temporaire.

Code:

---

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

int fibo_iteratif(int n) { int first = 0, second = 1;   int tmp;   while (n--) { tmp = first+second; first = second; second = tmp; }   return first; }

---

Une boucle while ou for, c'est la même chose.

* : parce qu'il en a d'autres comme celui de @SimonDecoline ou @Sve@r