Analyse de l’algorithme de Fibonacci
Cet article me fait penser à la manière dont j’ai été bluffé par ChatGPT qui me proposait l’usage de puissances n-ième de matrice [(0,1),(1,1)] par carrés et produits successifs... voir des versions encore plus optimisées (calcul de seuls 2 valeurs des matrices qui suffisent pour les calculs grâce à quelques invariants).
Signe non pas de l’intelligence de ChatGPT, mais de celui qui a proposé l’algorithme initial.
Curieux, ce principe d’avoir un vecteur contenant à l’indice 1, un autre vecteur.
J’ai essayé en OCaml... La bibliothèque Base de Jane Street fournit la fonction Hashtbl.find_or_add fib_table qui contient toute la logique de mémoization hormis la création de la table !... Cela paraissait plus simple... en revanche la construction récursive de fib (qui ne fait pas que bêtement s’appeler elle même) est trop complexe pour OCaml, il faut contourner !
> Curieux, ce principe d’avoir un vecteur contenant à l’indice 1, un autre vecteur :
Comme Scheme est un langage à typage dynamique, il est prudent d’étiqueter ses tableaux. L’étiquette est contenue dans la case d’indice 0 du vecteur à 2 cases, dont la seconde contient le vecteur qui contient les vraies données. Sinon n’importe quel tableau qui contiendrait n’importe quelles données pourrait être soumis au programme, avec des résultats erronés.