Prolog et Fibonacci


précédentsommairesuivant

I. Les algorithmes classiques.

I-A. Un petit rappel historique.

Ce rappel est extrait d'un article de WilkipediaFibanacci sur Wilkipedia
La suite de Fibonacci est l'une des suites mathématiques les plus connues. Elle doit son nom au mathématicien italien Leonardo Pisano, plus connu sous le pseudonyme de Fibonacci (1175 - 1250). Dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci, Fibonacci décrit la croissance d'une population de lapins :
« Possédant initialement un couple de lapins, combien de couples obtient-on en douze mois si chaque couple engendre tous les mois un nouveau couple à compter du second mois de son existence ? »
Ce problème est à l'origine de la suite dont le -ème terme correspond au nombre de paires de lapins au -ème mois. Dans cette population (idéale), on suppose que :

  • le premier mois, il y a juste une paire de lapereaux ;
  • les lapereaux ne sont pubères qu'à partir du deuxième mois ;
  • chaque mois, toute paire susceptible de procréer engendre effectivement une nouvelle paire de lapereaux ;
  • les lapins ne meurent jamais (donc la suite de Fibonacci est strictement croissante).

I-B. La définition mathématique de la suite.

Mathématiques
Sélectionnez
fibonacci(n) = n si n < 2
fibonacci(n) = fibonacci(n-1)+fibonacci(n-2)

I-C. Les algorithmes de base.

Dans cette section, nous abordons les deux algorithmes de base, le premier récursif particulièrement inefficace, et le second itératif, très performant.

I-C-1. L'algorithme naïf.

Le premier algorithme de calcul dérive directement de la définition mathématique :

Algorithme
Sélectionnez
fonction Fibonacci_naive(n : entier) : entier
variable retour : entier
début
  si n < 2 alors
    retour <- n
  sinon
    retour <- Fibonacci_naive(n-1) + Fibonacci_naive(n-2)
  fin si
  retourner retour
fin

I-C-2. L'algorithme itératif.

Bien évidement, une version itérative nettement plus efficace a été élaborée. Elle se base sur la construction du nombre à partir de 0 et 1, un nombre de la suite étant la somme des deux nombres le précédant.

Algorithme
Sélectionnez
fonction Fibonacci_iter(n : entier) : entier
variable compteur, val1, val2, val3, retour : entier
debut
  si n < 2 alors
    retour <- n
  sinon
    val1 <- 0
    val2 <- 1
    pour compteur de 2 à n par pas de 1 faire
      val3 <- val1 + val2
      val1 <- val2
      val2 <- val3
    fin pour
    retour <- val2
  fin si
  retourner retour
fin

I-D. Implémentation Prolog des algorithmes de base.

I-D-1. L'algorithme naïf.

Les fonctions n'existant pas en Prolog, on utilisera un prédicat naive_fib/2 le premier étant l'indice du second dans la suite des nombres de Fibonacci.

Prolog
Sélectionnez
naive_fib(X, X) :- X < 2, !.
naive_fib(X, Y) :-
  Idx1 is X - 1,
  Idx2 is X - 2,
  naive_fib(Idx1, A),
  naive_fib(Idx2, B),
  Y is A + B.

Cette version n'est pas très performante, on obtient ce résultat pour le calcul de Fibonacci(40) :

Console Prolog
Sélectionnez
14 ?- time(naive_fib(40,N)).
% 1,159,060,982 inferences, 340.16 CPU in 362.57 seconds (94% CPU, 3407437 Lips)

N = 102334155 ;

soit plus de 1 100 000 000 inférences et plus de 5 minutes 40 secondes pour calculer Fibonacci(40) !

I-D-2. L'algorithme itératif.

La boucle pour de l'algorithme est remplacée par un appel récursif terminal.
Le prédicat posséde 4 arguments. L'indice de boucle est décrémenté à partir de N pour pouvoir arrêter la boucle à 1 et éviter ainsi un cinquième argument, le maximum de l'indice de boucle.

Prolog
Sélectionnez
fib_iter(N, F) :-
    % si N est plus petit que 2, pas de calcul
	N < 2 -> F = N ;
	% Sinon il est lancé
	fib_iter_cal(0, 1, N, F).

% arg1 : l'avant dernier calcul
% arg2 : le dernier calcul
% arg3 : Indice de boucle de calcul en cours (arrêt à 1)
% arg4 : résultat final
fib_iter_cal(_F, F, 1, F) :- !.

fib_iter_cal(TT1, TT2, N, F) :-
	TT3 is TT1 + TT2,
	N1 is N - 1,
	fib_iter_cal(TT2, TT3, N1, F).

Ce code est nettement plus performant :

Console Prolog
Sélectionnez
time(fib_iter(100000, N)).
% 299,999 inferences, 0.67 CPU in 1.15 seconds (58% CPU, 446510 Lips)

Je vous épargne le résultat, il s'écrit avec 20 900 chiffres !

I-E. Conclusion.

Bien évidemment, l'algorithme itératif est nettement plus performant que l'algorithme naïf. Aucune autre méthode ne peut faire mieux en Prolog. Cependant, la puissance d'expression du langage permet d'utiliser d'autres concepts pour le calcul. Ces concepts sont exposés dans les chapitres suivants.


précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+