IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Prolog et Fibonacci

Cet article est destiné à montrer les possibilités de Prolog pour envisager le calcul des nombres de Fibonacci.
D'abord les algorithmes classiques sont montrés.
Ensuite d'autres méthodes sont évoquées, « mémoïsation », streams en liaison avec les « Open Lists », enfin les « DCG ». ♪

Article lu   fois.

L'auteur

Profil Pro

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

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 -ième terme correspond au nombre de paires de lapins au -iè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 évidemment, 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 quatre 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.

II. Utilisation de la mémoïsation

II-A. Qu'est-ce que la mémoïsation ?

Observons le développement du calcul de Fibonacci(5), les calculs les plus à gauche sont effectués en premier.

Graphe de calcul de Fibonacci(5)
Sélectionnez
                                                                fib(5)
                                                                  |
                                 _________________________________+______________________________
                                 fib(4)                                                    fib(3)
                                   |                                                         |
                 __________________+__________________                              _________+___________
                 fib(3)                         fib(2)                              fib(2)     fib(1) = 1 
                   |                              |                                   |
          _________+___________      _____________+_____________          ____________+____________            
          fib(2)     fib(1) = 1      fib(1) = 1       fib(0) = 0          fib(1) = 1     fib(0) = 0
            |
____________+____________
fib(1) = 1     fib(0) = 0

On constate que de nombreux calculs sont répétés inutilement, et si on peut les mémoriser, un important gain de temps est effectué.
Cette technique s'appelle la mémoïsation, dès qu'un résultat est connu, il est mémorisé pour pouvoir être récupéré plus tard.
Observons ce que cela donne, mémo indique que le résultat est mémorisé.

Graphe de calcul de Fibonacci(5)
Sélectionnez
                                                                fib(5)
                                                                  |
                                 _________________________________+_________________________________
                                 fib(4) mémo                                               fib(3)= 2
                                   |                                                         
                 __________________+___________________               
                 fib(3) mémo                  fib(2)= 1              
                   |                                                          
          _________+_______________     
          fib(2) mémo    fib(1) = 1        
            |
____________+____________
fib(1) = 1     fib(0) = 0

Dans le calcul, on devra s'assurer d'abord que le résultat n'est pas déjà connu, et s'il ne l'est pas, le calculer et le mémoriser. On obtient cet algo :

Algorithme
Sélectionnez
fonction fibonacci_memo(N : entier) : entier
variable retour : entier
variable existe : booleen
début
  existe <- existence de Fibonacci(N) dans la base de données
  si existe = vrai alors
    retour <- Fibonacci(N)
  sinon
    retour <- fibonacci_memo(N-1) + fibonacci_memo(N-2)
    // Maintenant Fibonacci(N) est connu, il faut l'enregistrer dans la base de données
    mémoriser le couple (N, Fibonacci(N))
  fin si
  retourner retour
fin

II-B. Une première méthode de mémoïsation

Prolog possède un mécanisme très simple de mémorisation, les prédicats dynamiques qui permettent d'ajouter « à runtime » des faits dans la base de données Prolog. On peut le faire par l'intermédiaire de trois prédicats : assert/1, asserta/1 et assertz/1 (mais qui est équivalent à assert/1). Un petit exemple permet de mieux comprendre :

Prolog
Sélectionnez
% déclaration des prédicats dynamiques (nom/arité)
:- dynamic pred1/2, pred2/2.

test :-
    % insertion normale dans la base de données
    assert(pred1(0,0)),
    assert(pred1(2,4)),
    assert(pred1(3,5)),
    
    % insertion en tête de base de données
    asserta(pred2(0,0)),
    asserta(pred2(2,4)),
    asserta(pred2(3,5)).

On obtient, entre autres, le contenu de la base de données Prolog par le prédicat listing/0. Après avoir enlevé certains renseignements ici inutiles, on obtient comme résultat :

Console Prolog
Sélectionnez
5 ?- listing.

:- dynamic pred1/2.

pred1(0, 0).
pred1(2, 4).
pred1(3, 5).

:- dynamic pred2/2.

pred2(3, 5).
pred2(2, 4).
pred2(0, 0).

Yes

On constate bien que les couples pred2 sont mémorisés dans l'ordre inverse de l'insertion dans la base de données. Cependant, il n'y a aucune différence au point de vue temps d'accès entre les deux prédicats

Les tuples fibo(N, FN) seront ajoutés à la base de données par l'intermédiaire de assert/1. On obtient donc le code Prolog suivant :

Prolog
Sélectionnez
% fibo/2 permet de mémoriser les résultats intermédiaires
% déclaration du prédicat dynamique (nom/arité)
:- dynamic (fibo/2).

% Lancement du calcul
fib_memo(N, F) :-
    % les deux premiers resultats sont memorises
    assert(fibo(0,0)),
    assert(fibo(1,1)),
    fib_memo_calcul(N, F).

% On vérifie que le calcul n'a pas déjà été effectué
fib_memo_calcul(N, F) :-
    fibo(N, F), !.

% En cas d'échec, on le calcule
fib_memo_calcul(N, F) :-
    N1 is N - 1,
    % Calcul de Fibonacci(N1)
    fib_memo_calcul(N1, F1),
    N2 is N - 2,
    % Le calcul de Fibonacci(N2) a déjà été fait, on peut le récupérer
    fibo(N2,F2),
    F is F1 + F2,
    % et on le mémorise dans la base de données
    assert(fibo(N, F)).

Les résultats sont honorables, même s'ils n'atteignent pas la performance du calcul itératif.

Console Prolog
Sélectionnez
3 ?- test(100000).
% 699,998 inferences, 28.03 CPU in 29.38 seconds (95% CPU, 24972 Lips)

II-C. Une seconde méthode de mémoïsation

La méthode précédente possède à mon avis le défaut « de ne pas laisser l'environnement aussi propre que lorsque je l'avais trouvé ».
On peut mémoriser les résultats intermédiaires en utilisant une bibliothèque toute faite, les listes d'assocations. Ces listes d'associations utilisent les techniques d'arbres AVL pour des insertions et des recherches en O(Log (N)). Les détails sur cette bibliothèque peuvent être trouvés iciLes listes d'associations en SWI-Prolog..
Le code obtenu ressemble comme un frère au précédent.

Prolog
Sélectionnez
% fibonacci avec des listes d'associations
fib_assoc(N, X) :-
    % creation de la liste d'association vide
    empty_assoc(As0),
    % on insere les deux premieres valeurs
    put_assoc(0, As0, 0, As1),
    put_assoc(1, As1, 1, As2),
    % et on lance le calcul
    fib_assoc_calcul(N, X, As2, _).

fib_assoc_calcul(N, X, As1, As1 ):-
    get_assoc(N, As1, X), !.

fib_assoc_calcul(N, X, As0, As3) :-
    N1 is N-1,
    N2 is N-2,
    % Calcul de Fibonacci(N1)
    fib_assoc(N1, FN1, As0, As1),
    % Le calcul de Fibonacci(N2) a déjà été fait, on peut le récupérer
    get_assoc(N2, As1, FN2),
    X is FN1 + FN2,
    % et on le mémorise
    put_assoc(N, As1, X, As3).

Les résultats sont nettement moins bons :

Console Prolog
Sélectionnez
6 ?- time(fib_assoc(50000, N)).
% 5,991,280 inferences, 5.47 CPU in 5.61 seconds (97% CPU, 1095548 Lips)

Le calcul de Fibonacci(100 000) explose la pile d'exécution !

III. Utilisation des « Open Lists »

III-A. Que sont les Open Lists ?

Dans une liste « normale », le dernier élément est la liste vide : exemple [1,2,3|[]].
Les Open Lists sont des listes particulières où le dernier élément n'est pas défini : exemple [1,2,3|_].
Considérons ce petit programme :

Prolog
Sélectionnez
test :-
    L = [1,2,3|_],
    (   member(1, L) -> format('1 présent dans ~w~n', [L]);format('1 absent dans ~w~n', [L])),
    (   member(3, L) -> format('3 présent dans ~w~n', [L]);format('3 absent dans ~w~n', [L])),
    (   member(5, L) -> format('5 présent dans ~w~n', [L]);format('5 absent dans ~w~n', [L])).

La sortie obtenue est :

Console Prolog
Sélectionnez
10 ?- test.
1 présent dans [1, 2, 3|_G272]
3 présent dans [1, 2, 3|_G272]
5 présent dans [1, 2, 3, 5|_G281]

On constate que lorsque l'élément est présent, la liste n'est pas modifiée, lorsqu'il est absent, il est ajouté en fin de liste. Remarquons au passage que contrairement à ce qui se passe habituellement en Prolog, bien que la liste soit modifiée, elle est toujours unifiée avec la même variable.

III-B. Simulation d'un stream par une Open List

Il est possible d'attacher une procédure à une Open List, on peut ainsi simuler un stream.
Le code suivant est inspiré de cette pageLes stream en Prolog. when(@Condition, :Goal) est un prédicat qui permet de geler l'exécution de :Goal tant que la condition @Condition n'est pas à true. En Prolog, le « @ » en début de nom de variable signifie que l'argument n'est pas encore instancié, le « : » signifie que l'argument est un métaargument.
Ce code permet de calculer la suite des puissances de 2, on remarquera que la création du stream est faite avant la création de l'Open List.

Prolog
Sélectionnez
% arg1 : la procédure à appliquer au stream (ici un prédicat à deux arguments)
% arg2 : l'élément d'initialisation du calcul
% arg3 : le stream 
make_stream(Pred, Head, OpenList) :-
   when(nonvar(OpenList), 
        (
          % on construit l' Open List
          OpenList = [Head|Rest],
          % on applique le prédicat de calcul
          call(Pred, Head, Next),
          % on construit récursivement l' Open List
          make_stream(Pred, Next, Rest)
        )).
        
% le prédicat de calcul des puissances
double(X, Y) :-
    Y is X * 2.

% le stream permettra de calculer la liste des puissances de 2
tests :-
    % création du stream
    make_stream(double, 1, OpenList),
    OpenList = [_, _, _, _|X],
    format('Les quatre premières puissances de 2 sont ~w~n', [OpenList]),
    X = [_, _, _, _|_Y],
    format('Les huit premières puissances de 2 sont ~w~n', [OpenList]).

On obtient :

Console Prolog
Sélectionnez
12 ?- test.
Les quatre premières puissances de 2 sont [1, 2, 4, 8|_G312]
Les huit premières puissances de 2 sont [1, 2, 4, 8, 16, 32, 64, 128|_G466]

De plus amples explications sur le prédicat when/2 peuvent être trouvées iciLe prédicat when/2.
De plus amples explications sur le prédicat nonvar/1 peuvent être trouvées iciLe prédicat nonvar/1.

III-C. Le calcul des nombres de Fibonacci avec les Open Lists et les streams

Par les streams, on obtient une liste des nombres de Fibonacci.
La construction de l'Open List se fait de manière itérative.
Le calcul des nombres est un calcul itératif semblable au calcul itératif du I-C-2.

Prolog
Sélectionnez
% Construction de l' Open List
make_OpenList(0, OpenList, OpenList):- !.

make_OpenList(N, L1,L2) :-
    N1 is N-1,
    make_OpenList(N1, [_|L1], L2).

% creation du stream de calcul
% ici le prédicat de calcul a besoin de 2 arguments en entree !
make_stream_fib(Pred, First, Second, OpenList) :- 
   when(nonvar(OpenList), 
        ( 
          OpenList = [Second |Rest], 
          call(Pred, First, Second, Next),
          make_stream_fib(Pred, Second, Next, Rest) 
        )). 

fib_OpenList(N) :-
         make_stream_fib(fib_OpenList, 0, 1, OpenList),
         make_OpenList(N, _, OpenList).
         
% calcul effectif du nombre de Fibonacci.         
fib_OpenList(X,Y,Z) :-
    Z is X + Y.

Les performances sont correctes :

Console Prolog
Sélectionnez
11 ?- time(fib_OpenList(30000)).
% 360,029 inferences, 0.73 CPU in 0.89 seconds (83% CPU, 490252 Lips)

Remarquons que la génération de l'Open List par make_OpenList prend 60 000 inférences.

IV. Utilisation des DCG

Les DCG « Definite Clause Grammar » permettent d'écrire de façon aisée en Prolog des règles de grammaire.

IV-A. Exemple de DCG

Regardons ces DCG pour une grammaire très simple d'expressions numériques :

Prolog
Sélectionnez
expression --> terme, suite_terme.
suite_terme --> [].
suite_terme --> [+], expression.
terme --> facteur, suite_facteur.
suite_facteur --> [].
suite_facteur --> [*], terme.
facteur --> [I], {integer(I)}.
facteur --> ['('], expression, [')'].

La première règle signifie qu'une expression est un terme suivi d'un élément appelé suite_terme.
Le deuxième et la troisième règle définissent suite_terme. suite_terme peut n'être rien (deuxième règle) ou l'enchaînement du signe + et d'une expression.
La règle facteur --> [I], {integer(I)}. indique qu'un facteur peut être un nombre et qu'un nombre est reconnu comme vérifiant le prédicat integer/1. Le code entre accolades est interprété comme du Prolog pur.
Après compilation du code comme un code Prolog, on peut tester les règles :

Console Prolog
Sélectionnez
13 ?- expression([1,+,3,*,'(',2,+,4,')'],[]).

Yes
14 ?- expression([1,-,3,*,'(',2,+,4,')'],[]).

No

La deuxième expression n'est pas reconnue puisque '-' n'est pas défini par notre grammaire.
On peut obtenir la conversion en Prolog des règles DCG par le prédicat listing/0.

Prolog
Sélectionnez
expression(A, C) :-
        terme(A, B),
        suite_terme(B, C).

terme(A, C) :-
        facteur(A, B),
        suite_facteur(B, C).

suite_terme(A, A).
suite_terme([+|À], B) :-
        expression(A, B).

facteur([A|C], B) :-
        integer(A),
        B=C.
facteur(['('|A], C) :-
        expression(A, B),
        B=[')'|C].

suite_facteur(A, A).
suite_facteur([*|À], B) :-
        terme(A, B).

On constate que Prolog ajoute automatiquement deux arguments aux prédicats et qu'on retrouve la structure d'Open Lists (prédicas suite_terme, facteur …).
Des renseignements complémentaires sur les DCG peuvent être trouvés ici. Des renseignements sur les DCG en SWI-Prolog peuvent être trouvés ici.

IV-B. La version naïve en DCG

La version de l'algorithme naïf peut s'écrire sous cette forme:

Prolog
Sélectionnez
fib_dcg_naif(0,0) --> [].
fib_dcg_naif(1,1) --> [].

fib_dcg_naif(X, FX) -->
    {X > 1,
     X1 is X-1, 
     X2 is X - 2},
     fib_dcg_naif(X1, FX1),
     fib_dcg_naif(X2, FX2),
     {FX is FX1 + FX2}.

Les performances sont à la hauteur de la méthode du calcul des nombres de Fibonacci !

Console Prolog
Sélectionnez
24 ?- time(fib_dcg_naif(25, X,_,_)).
% 971,137 inferences, 10.00 CPU in 10.05 seconds (100% CPU, 97114 Lips)

X = 75025 ;

No

Le simple calcul fib_dcg_naif(30, X). fait exploser la pile d'exécution.

IV-C. Une méthode itérative de calcul des nombres de Fibonacci avec les DCG.

Les méthodes suivantes sont inspirées de cet article
La première méthode est basée sur le calcul itératif, les résultats, sous la forme de tuples fib(Nombre, Valeur), sont mémorisés dans une liste. La liste est initialisée avec les deux premières valeurs, Fibonacci(0) et Fibonacci(1).

Prolog
Sélectionnez
% Le lancement du calcul 
fib_dcg_ver1(X) :-
    fib_dcg_ver1_calc(X, [fib(1,1), fib(0,0)], _, _).
    
% ici la valeur recherchée est trouvée
fib_dcg_ver1_calc(X, [X|_]) --> [].

% Sinon on calcule la valeur suivante
% En s'assurant qu'on n'a pas dépassé la valeur recherchée
fib_dcg_ver1_calc(X, [A, B]) -->
  {gt(X, A)},
  fib_suivant_ver1(A, B, Next_Fib),
  fib_dcg_ver1_calc(X, [Next_Fib, A]).

% calcul de la valeur suivante
fib_suivant_ver1(fib(Idx1, Num1), fib(_Idx2, Num2), fib(Idx3, Num3)) -->
    [],
    {Idx3 is Idx1 + 1,
    Num3 is Num1 + Num2}.

gt(fib(A, _FA), fib(X, _FX)) :-
    À >= X.

Les résultats sont intéressants :

Console Prolog
Sélectionnez
8 ?- time(fib_dcg_ver1(100000, _)).
% 799,994 inferences, 0.80 CPU in 1.16 seconds (69% CPU, 1003914 Lips)

IV-C-1. Amélioration de la méthode

On peut améliorer la rapidité du code en introduisant un cut bien placé : lorsque la valeur a été trouvée, il est inutile de continuer.

Prolog
Sélectionnez
% Le lancement du calcul 
fib_dcg_ver2(X) :-
    fib_dcg_ver2_calc(X, [fib(1,1), fib(0,0)], _,_).

% version avec un cut
fib_dcg_ver2_calc(X, [X|_]) --> [], {!}.

fib_dcg_ver2(X, [A, B]) -->
  fib_suivant_ver2(X, A, B, Fib1),
  fib_dcg_ver2_calc(X, [Fib1, A]).

fib_suivant_ver2(X, fib(Idx1, Num1), fib(Idx2, Num2), fib(Idx3, Num3)) -->
  [],
  { Idx3 is Idx1 + 1,
    Num3 is Num1 + Num2 }.

Le gain est important en nombre d'inférences :

Console Prolog
Sélectionnez
10 ?- time(fib_dcg_ver2(100000, _)).
% 499,999 inferences, 0.61 CPU in 1.08 seconds (57% CPU, 820511 Lips)

IV-D. Le calcul des nombres de Fibonacci avec mémorisation des résultats

Les méthodes précédentes n'utilisent pas toute la puissance des DCG. On peut mémoriser les résultats intermédiaires dans une liste. Attention, il n'est pas question de mémoïsation, les résultats ne sont pas réutilisés, la mémoïsation sera évoquée dans le chapitre suivant.
Au cours du calcul, les résultats seront insérés en fin de la liste des nombres en utilisant la technique des différences de listes : cette méthode permet de concaténer n'importe quelles listes en une seule inférence, alors que append/3 est en O(N) où N est la longueur de la première chaîne.

IV-D-1. Le mécanisme des différences de listes.

Une liste écrite sous la forme d'une différence des listes s'écrit de manière générale X-Y. En utilisant les possibilités des Open Lists, on peut les écrire sous la forme [X|Y]-Y. Ainsi, pour concaténer des listes écrites en différences, on utilise le mécanisme suivant :

Prolog
Sélectionnez
append_dl(X1-X2, X2-X3, X1-X3).

Observons ce qui se passe lors de la concaténation avec cet exemple :

Console Prolog
Sélectionnez
append_dl([1,2,3|T]-T, [4,5,6|U]-U, Z-U).

On constate que
X1 est unifié avec [1,2,3|T].
X2 est unifié avec T et [4,5,6|U], donc T est unifié avec [4,5,6|U] et par voie de conséquence X1 est unifié avec [1,2,3,4,5,6|U].
La concaténation s'est faite en une seule inférence !
La transformation d'une différence de listes en liste normale est très simple et se fait en temps constant, il suffit de concaténer la différence de listes avec la liste vide représentée par []-[] :

Code Prolog
Sélectionnez
dl_to_lf(DL, LF):-
    append_dl(DL, []-[], LF-[]).

IV-D-2. Le calcul des nombres de Fibonacci avec mémorisation

Comme dans la méthode itérative, les deux derniers nombres calculés servent au calcul du suivant. Le premier des deux nombres est mémorisé au moment du calcul avant d'être « oublié » par la boucle de calcul. Remarquons que insere_successeur passe de 2 arguments dans les DCG à 4 dans les règles Prolog. Le troisième argument peut être considéré comme un argument d'entrée de la clause (il contient la liste des résultats déjà connus) et le quatrième comme un argument de sortie (il contient un résultat de plus).

Prolog
Sélectionnez
% la bonne valeur est trouvée
fib_dcg_memo(X, [X|_]) --> [].

% les deux derniers nombres calculés servent au calcul du suivant
fib_dcg_memo(X, [A, B]) -->
  fib_dcg_memo_suivant(X, A, B, Fib1),
  fib_dcg_memo_suivant(X, B, Fib1, Fib2),
  fib_dcg_memo(X, [Fib1, Fib2]).

% Calcul du nombre de Fibonacci, somme des deux précédents
% le premier est mémorisé
fib_dcg_memo_suivant(X, fib(Idx1, Num1), fib(Idx2, Num2), fib(Idx3, Num3)) -->
  insere_successeur(X, fib(Idx1, Num1)),
  { Idx3 is Idx2 + 1,
    Num3 is Num1 + Num2 }.

% insertion en fin de liste d'un nombre de Fibonacci
% On s'assure qu'on n'a pas dépassé le nombre cherché
insere_successeur(A, B, Old, New) :-
  gt(A, B),
  append_dl(Old, [B|T2] - T2, New).

gt(fib(A, _FA), fib(B, _FB)) :-
    À >= B.

append_dl(X1-X2, X2-X3, X1-X3).

Le lancement du calcul peut se faire par :

 
Sélectionnez
fib_dcg_demo(X, FX, Lst_Fibo) :-
     % fib_dcg_memo(arg1, arg2, arg3, arg4).
     % arg1 : le tuple fib(X, FX) recherché
     % arg2 : la liste contenant les deux premiers résultats connus nécessaires pour le calcul
     % arg3 : la liste des tuples résultats mémorisés. À l'initialisation elle est vide 
     % donc initialisée à T-T, car c'est une différence de listes
     % arg4 : la liste des tuples résultats connus après le calcul
    fib_dcg_memo(fib(X, FX), [fib(0,0), fib(1,1)], T-T, Dl_Lst_Fibo),
    % conversion de la liste des tuples en liste "normale"
    dl_to_lf(Dl_Lst_Fibo, Lst_Fibo).

Exemple de calcul :

Console Prolog
Sélectionnez
?- fibo(8, FX, LstFibo).

FX = 21,
LstFibo = [fib(0, 0), fib(1, 1), fib(2, 1), fib(3, 2), fib(4, 3), fib(5, 5), fib(6, 8), fib(7, 13)] ;

No

À cause de la création de la liste des nombres de Fibonacci, la méthode ne permet pas d'aller plus loin que Fibonacci(50000). Les résultats sont honorables :

Console Prolog
Sélectionnez
?- time(fib_dcg_memo(fib(50000, FX), [fib(0,0), fib(1,1)], T-T, _)).
% 425,001 inferences, 0.64 CPU in 0.73 seconds (88% CPU, 663416 Lips)

75 ?- time(fib_dcg_memo(fib(30000, FX), [fib(0,0), fib(1,1)], T-T, _)).
% 255,001 inferences, 0.28 CPU in 0.31 seconds (91% CPU, 906670 Lips)

Les calculs sont plus rapides que pour la méthode avec les streams :

Console Prolog
Sélectionnez
?- time(fib_OpenList(30000)).
% 360,029 inferences, 0.73 CPU in 0.89 seconds (83% CPU, 490252 Lips)

IV-E. Le calcul des nombres de Fibonacci avec mémoïsation

Dans cette partie, on utilise la méthode récursive, mais les résultats sont mémorisés pour ne pas avoir à les recalculer. La recherche du résultat dans la liste se faisant à l'aide du prédicat member/2, on ne peut pas utiliser la technique des différences de listes. Voir iciLes Open Lists.
Les couples seront donc insérés en tête de la liste des résultats déjà connus.
Les règles de grammaire sont très simples : l'obtention d'un nombre de Fibonacci s'obtient soit par la recherche dans une liste, soit par le calcul des deux nombres précédents.

Code Prolog
Sélectionnez
% premiere possibilité , on trouve le résultat dans la liste
fib_dcg_memoisation(A) -->
    fib_dcg_memoisation_recherche(A), {!}.

% seconde possibilité, on calcule le nombre
fib_dcg_memoisation(A) -->
    fib_dcg_memoisation_calcul(A).

% La recherche est le simple test member/2
fib_dcg_memoisation_recherche(A, Lst, Lst)  :-
    member(A, Lst).

% Le calcul est le calcul classique récursif.
fib_dcg_memoisation_calcul(fib(X, FX)) -->    
    {
        X1 is X-1,
        X2 is X-2
    },
    fib_dcg_memoisation(fib(X1, FX1)),
    fib_dcg_memoisation(fib(X2, FX2)),
    {
          FX is FX1 + FX2
    },
    % le résultat est mémorisé
    ajoute_fib_ver1(fib(X,FX)).


% mémorisation du nombre dans la liste
ajoute_fib_ver1(A, Old, [A | Old]).
    

fib_dcg_memoisation_lance(X, L) :-
    fib_dcg_memoisation(X, [fib(1,1), fib(0,0)], L).

Exemple de résultat :

Console Prolog
Sélectionnez
32 ?- fib_dcg_memoisation_lance(fib(7,X), L).

X = 13,
L = [fib(7, 13), fib(6, 8), fib(5, 5), fib(4, 3), fib(3, 2), fib(2, 1), fib(1, 1), fib(0, 0)] ;

No

Les performances ne sont pas extraordinaires, près de 850 000 inférences pour le calcul de Fibonacci(50 000) :

 
Sélectionnez
33 ?- time(fib_dcg_memoisation_lance(fib(50000,_), _)).
% 849,988 inferences, 0.80 CPU in 0.96 seconds (83% CPU, 1066652 Lips)

Yes

V. Conclusion

On peut écrire un programme de test :

Prolog
Sélectionnez
% programme de test
% N est le rang du nombre de Fibonnaci à calculer
test(N) :-
    retractall(fibo(_,_)),
    writeln('fib_iter'), time(fib_iter(N, _)), nl,
    writeln('fib_memo'), time(fib_memo(N, _)), nl,
    writeln('fib_assoc'), time(fib_assoc(N, _)), nl,
    writeln('fib_OpenList'), time(fib_OpenList(N)), nl,
    writeln('fib_dcg_ver1'), time(fib_dcg_ver1(fib(N, _))), nl,
    writeln('fib_dcg_ver2'), time(fib_dcg_ver2(fib(N, _))), nl,
    writeln('fib_dcg_memo'), time(fib_dcg_memo(fib(N, _), [fib(0,0), fib(1,1)], T-T, _)), nl,
    writeln('fib_dcg_memoisation'), time(fib_dcg_memoisation(fib(N, _), [fib(1,1), fib(0,0)],_)).

On obtient les résultats suivants pour le calcul de Fibonacci(30 000) :

Console Prolog
Sélectionnez
1 ?- test(30000).
fib_iter
% 89,999 inferences, 0.13 CPU in 0.13 seconds (96% CPU, 719992 Lips)

fib_memo
% 209,998 inferences, 0.94 CPU in 1.07 seconds (88% CPU, 223998 Lips)

fib_assoc
% 3,433,516 inferences, 2.11 CPU in 2.19 seconds (96% CPU, 1627741 Lips)

fib_OpenList
% 361,667 inferences, 0.69 CPU in 0.89 seconds (77% CPU, 526061 Lips)

fib_dcg_ver1
% 239,994 inferences, 0.30 CPU in 0.31 seconds (94% CPU, 808401 Lips)

fib_dcg_ver2
% 149,998 inferences, 0.20 CPU in 0.21 seconds (95% CPU, 738452 Lips)

fib_dcg_memo
% 255,001 inferences, 0.23 CPU in 0.26 seconds (89% CPU, 1088004 Lips)

fib_dcg_memoisation
% 510,025 inferences, 0.33 CPU in 0.38 seconds (86% CPU, 1554362 Lips)

Yes

En éliminant quatre méthodes qui ne dépassent pas le calcul de Fibonacci(50 000), on obtient ce résultat pour le calcul de Fibonacci(100 000) :

Console Prolog
Sélectionnez
8 ?- test(100000).
fib_iter
% 299,999 inferences, 0.69 CPU in 1.05 seconds (66% CPU, 436362 Lips)

fib_memo
% 699,998 inferences, 28.52 CPU in 29.69 seconds (96% CPU, 24548 Lips)

fib_dcg_ver1
% 799,994 inferences, 0.70 CPU in 1.17 seconds (60% CPU, 1137769 Lips)

fib_dcg_ver2
% 499,999 inferences, 0.63 CPU in 1.08 seconds (58% CPU, 799998 Lips)

Yes

On constate que la version la plus performante en nombre d'inférences est sans contestation possible la version itérative et que la version avec mémoïsation est très lente par rapport à la version écrite à l'aide des DCG sans le cut.

VI. Téléchargements

Le fichier « fibonacci.pl » donnant le code de tous les calculs décrits dans cet article est téléchargeable ici.
Il est aussi possible de télécharger une version PDF ici.
.

VII. Remerciements

Je tiens à remercier jbarreau-mainson pour sa relecture attentive, Gorgonite Alp et pcaboche pour leurs conseils avisés. :)

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