TROIS ALGORITHMES POUR LA SUITE DE FIBONACCI

Commentaire de us_30 le 09/07/2006 17:18:16

Salut,

Oui, c'est ce que je voulais demander. Donc quelle version utiliser ?

Amicalement,
Us.

Commentaire de us_30 le 09/07/2006 18:43:31

Re-salut,

OK, merci.

JE vais tout de même de tester tes 2 premiers algo qui fonctionnent sous VB5... JE suis trés étonné de la trés trés faible performance de ton 1er algo, dit "naïf"... c'est à dire qui utilise la réccurrence de la définition... En effet, j'obtiens un peu 9 secondes (sur mon PC)... Je veux bien admettre que ce n'est pas l'algo le plus performant, mais delà à obtenir un temps si long pour juste quelques sommes !...

J'ai refait ce premier algo à ma sauce, et c'est sans comparaison. J'obtiens 0,002 seconde ! (et en Double)

JE pense qu'il y a un truc qui doit faire chuter les perfs...


Voici mon algo :

===

Function Fibonacci(ByVal n As Integer) As Double
'Suite des nombres de finabocci

Dim m1 As Double, m2 As Double, t As Integer, temps As Double
Finabocci = 1
m1 = 1: m2 = 1

temps = Timer
For t = 3 To n
Fibonacci = m1 + m2
m1 = m2
m2 = Fibonacci
Next t
MsgBox Timer - temps

End Function

===

Voilà... c'est une première remarque...

Pour ton second algo, j'obtiens 0,0006 seconde, donc toujours mieux...

A+
Amicalement,
Us.

Commentaire de Cacophrene le 10/07/2006 08:14:07

Salut !

La version que tu me proposes ne correspond pas à mon premier algorithme. Il y a deux raisons à cela : la première, c'est bien évidemment la différence de temps vertigineuse entre les deux algorithmes (oui, ne rêvons pas, 0,002 secondes pour un algo exponentiel, c'est douteux). La seconde, c'est que tu sauvegardes le résultat m1 + m2 et que tu opères une substitution exactement comme mon second algorithme avec fonction auxiliaire. Le premier algorithme, quant à lui, est bel et bien naïf parce que son coût en temps est prohibitif (comme tu as pu le voir... 9 secondes !). Sa complexité exponentielle (en O(phi ^ n) avec phi le nombre d'or) indique que pour calculer Fibonacci(32), on doit s'attendre à plusieurs millions d'opérations (le calcul exact importe peu, surtout avec la notation de Landau). Pourquoi ? Tout simplement parce qu'on demande de calculer deux fois toutes les valeurs. C'est ce qui se passe lorsque l'on écrit Fibonacci (n - 1) + Fibonacci (n - 2). Le programme commence par calculer Fibonacci (n - 1), qui demande Fibonacci(n - 2) et Fibonacci (n - 3)... Mais Fibonacci(n - 2) demande Fibonacci(n - 3) et Fibonacci (n - 4), etc... Nous recalculons sans cesse les MÊMES valeurs, et dans une telle mesure que cela devient ridicule.Ton algorithme, lui, ne fait pas tous ces calculs. Il en fait beaucoup moins. Pour le décalage, je suis étonné et je ne vois pas où est l'erreur... Attention je commence à zéro et pas à un (serait-ce la raison ?). Si tu as de plus amples indications à me fournir pour corriger ce problème, je suis preneur.

Cordialement,
Cacophrène

Commentaire de Cacophrene le 10/07/2006 11:03:35

Bonjour !

La mesure de la complexité d'un algorithme peut se faire selon trois méthodes :

1. Le meilleur des cas possibles
2. Le cas moyen (coût moyen)
3. Le pire des cas possibles (coût maximal)

Par exemple, l'algorithme du tri rapide (quicksort) est quadratique (en O(n²)) dans le pire des cas, et quasi-linéaire (en O(n * log n)) dans le cas moyen.

Ici, je propose trois algorithmes utilisant des formules connues :

a) Un algorithme naïf de complexité exponentielle O(phi ^ n).
b) Un algorithme évolué de complexité linéaire
c) Un algorithme avec calcul matriciel de complexité logarithmique.

La complexité est ici mesurée en nombre d'additions à effectuer. Il n'est pas question d'optimisation de code. Les trois algorithmes sont, dans leur genre propre, déjà optimisés. Toute amélioration comme par exemple sauvegarder la somme (comme l'a fait us_30) revient à changer d'algorithme et donc de complexité. C'est la raison pour laquelle nous obtenons des temps si différents.

Et de répéter, à la suite de Patrice99 qui l'a dit très justement : rien à voir avec l'optimisation. Trois algos distincts, trois complexités distinctes, et donc trois performances distinctes.

Cordialement,
Cacophrène

Commentaire de Cacophrene le 10/07/2006 13:27:16

Salut !

Pour te répondre, je te propose de reprendre en guise d'exemple deux des algorithmes qui figurent dans ma source ici même. Voyons d'abord le premier algo :

===
Public Function Fibonacci(n As Long) As Long
    Select Case n
        Case 0, 1
            Fibonacci = 1
        Case n
            Fibonacci = Fibonacci(n - 1) + Fibonacci(n - 2)
    End Select
End Function
===

Nous utilisons ici la définition classique de la suite de Fibonacci. Pour déterminer la complexité de cet algo, il suffit de considérer que la relation par récurrence F(n) = F(n - 1) + F(n - 2) a pour équivalent la formule de Binet :

1/Racine(5) * [((1 + Racine(5)) / 2) ^ n + ((1 - Racine(5)) / 2) ^ n]

Si nous passons à la limite pour n tendant vers l'infini, il ne reste que le premier terme (avec phi le nombre d'or), et donc 1 / Racine(5) * phi ^ n donne, en notation de Landau, un O(phi ^ n). Quitte à être moins précis, on peut montrer par récurrence que l'on est en O(2 ^ n). C'est moins précis mais ça revient "presque" au même : nous sommes dans l'idée d'une complexité exponentielle. Nous mesurons la difficulté d'une tâche à accomplir. "Intrinsèque" oui et non. Il n'y a pas de complexité "absolue". Changer d'algorithme fait changer de complexité.

Considérons maintenant le deuxième algo :

===
Public Function FastFibonacci(n As Long) As Long
    FastFibonacci = Auxiliary(1, 1, n)
End Function

Private Function Auxiliary(a As Long, b As Long, n As Long) As Long
    Select Case n
        Case 0
            Auxiliary = a
        Case n
            Auxiliary = Auxiliary(b, a + b, n - 1)
    End Select
End Function
===

Ici, tu vois que l'appel récursif à Auxiliary(b, a + b, n - 1) indique que nous avons en tout n - 1 additions à effectuer (on peut formaliser davantage au besoin). Nous sommes donc dans le cadre d'une complexité linéaire, soit en notation de Landau : O(n).

Or, comme tu me le diras, entre ces deux algos, il n'y a en fait qu'une meilleure utilisation des opérations et surtout des variables, ce qui évite de recalculer sans cesse les mêmes valeurs. Cette meilleure utilisation conduit à une grande amélioration des performances.

C'est un peu la même chose pour les algorithmes d'exponentiation classique et d'exponentiation rapide. Si j'écris :

Function Power(x As Integer, n As Integer) As Integer
Select Case n
  Case 0
   Power = 1
  Case n
   Power = x * Power(x, n - 1)
End Select
End Function

Dans ce cas je suis dans le cadre d'une complexité linéaire. Or si j'utilise une "astuce" pour réduire le nombre d'opérations, je peux tomber dans une complexité meilleure, logarithmique, en rédigeant :

Function FastPower(x As Integer, n As Integer) As Integer
Select Case n
  Case 0
   FastPower = 1
  Case 1
   FastPower = x
  Case n
    If n Mod 2 = 0 Then
     FastPower = (x * x) ^ (n \ 2)
    Else
     FastPower = x * (x * x) ^ (n \ 2)
    End If
End Select
End Function

Tu vois bien qu'il s'agit d'une autre présentation, pas foncièrement très différente de la précédente, hormis que nous avons, presque sans y songer, transformer un algo rapide en un algo beaucoup plus rapide.

Conclusion : La complexité est une mesure de l'efficacité des algorithmes, indépendamment du matériel (langage, processeur, compilateur, etc...). Et c'est aux API que l'on peut demander une approche plus expérimentale de la question, par le biais de moyennes. Un bon article Wikipédia sur le sujet : http://fr.wikipedia.org/wiki/Complexité_algorithmique

Voilà. J'espère avoir répondu aussi clairement que possible à la question.

Cordialement,
Cacophrène

Commentaire de Patrice99 le 10/07/2006 13:47:07

Ha ! je crois que j'ai dit une connerie : c'est vrai qu'avec un algo récursif, on ne peut pas toujours stocker facilement une variable sans changer complètement d'algo, tu dois avoir raison :-)
Maintenant, pour éviter le ridicule de mon intervention, il faudrait que je trouve un moyen de stocker cette variable quelque part, mais à priori, cela risque fort de ressembler à du super-bricolage à la mord-moi-l'noeud (ou alors carrément génial ?), à supposer même que cela soit possible sans changer la complexité de l'algo ! bigre !

Commentaire de Patrice99 le 10/07/2006 16:26:14

ou bien en utilisant un tableau global :
si résultat(n) déjà calculé alors retourner le résultat
faut voir, ça peut peut-être marcher finalement, mais c'est toujours bordélique de mélanger des variables globales avec du récursif.

Commentaire de Cacophrene le 10/07/2006 20:31:54

Salut !

Merci pour ta note, jean_marc_n2. C'est toujours sympa quand une source plaît ou sert à quelqu'un.

Merci encore,
Cacophrène

Commentaire de Cacophrene le 11/07/2006 07:44:49

Salut !

D'accord, je comprends maintenant... Mon problème c'est que je suis parti de la définition suivante :

F : N -> N tel que
                     F(0) = 1
                     F(1) = 1
                     F(n) = F(n - 1) + F(n - 2)

Bon je corrige tout ça pour la définition suivante :

F : N -> N tel que
                     F(0) = 0
                     F(1) = 1
                     F(n) = F(n - 1) + F(n - 2)

Merci pour ces indications et la note. Pour le troisième algo, tu as effectivement raison. Cela revient aux deux formules que tu cites. Pour la clarté, je suis aussi de ton avis. La raison vient du fait que ce programme est une traduction en VB d'une version en Caml où les opérateurs peuvent être réutilisés pour autre chose que leur utilisation de départ. Voici ce que ça donne :

===
(* Multiplication matricielle *)
let ( * ) a b = Array.init 2 (fun i -> Array.init 2 (fun j -> a.(i).(0) * b.(0).(j) + a.(i).(1) * b.(1).(j)))

(* Exponentiation rapide matricielle *)
let rec ( ** ) a = function
| 0 -> a
| 1 -> a
| n when n mod 2 = 0 -> (a * a) ** (n / 2)
| n -> a * (a * a) ** (n / 2)

let wild_fibonacci n = ([| [|1 ; 1|] ; [|1 ; 0|] |] ** n).(0).(0)
===

Evidemment, sous ces conditions, * n'est plus la multiplication des entiers mais celle des matrices, et ** n'est plus la puissance d'un entier mais celle d'une matrice. Les formules paraissent alors plus claires, surtout dans la fonction d'exponentiation rapide ( ** ) qui a "presque" la même tête que dans le cas des entiers. Dommage... je ne crois pas que l'on puisse en faire autant en VB, et les appels de fonctions ne sont pas aussi parlants.

Pour le code le plus optimisé concernant une plage de valeurs, je crois qu'on peut répondre de façon assez simple :

1. Si les valeurs de n sont petites, les trois algos "se valent en pratique".

2. Si les valeurs sont très grandes, seul le troisième algo est vraiment efficace (ou alors la formule de Binet qu'il ne faut pas non plus oublier. On peut la réaliser très vite en supprimant le second terme trop petit et utiliser l'exponentiation rapide pour faire un calcul très rapide et sans les notions mathématiques plus "raffinées" que sont les matrices).

3. Si les données ont des propriétés singulières, mieux vaut sans doute reprogrammer quelque chose pour elles seules.

Par exemple, quand on programme la multiplication des polynômes ou des entiers, on sait qu'on aura une mauvaise complexité... quand les valeurs sont immenses, mieux vaut aller voir du côté de Fourier. Mais si c'est pour faire 10 * 5, eh eh, c'est un peu exagéré ;-)

Cordialement,
Cacophrène

Commentaire de jean_marc_n2 le 11/07/2006 10:18:06

Hello,

Par exemple les algorithmes de tris: QuickSort (complexité moyennee n N.logN) devient très mauvais quand N est raisonnablement petit ET que le tableau est "presque" trié (Voir D.Knuth, The Art of Computer Programming, Volume 3 "Sorting and Searching", Chapitre 5.2.2). Dans ce cas, un tri à bulle (complexité en N^2) devient meilleur car pour ce cas particulier, la complexité tend à devenir plus ou moins O(n) alorq que QuickSort "devient" en O(n^2).

Il y a pas mal d'exemples de ce type. On peut aussi citer l'utilisation des tables de hachage. Elles garantissent en général un accès en O(1), mais dans certains cas dégénérés introduisant des collisions, l'emploi d'une recherche dichotomique (en N.Log N) est plus efficace.

La mesure de la complexité est un art difficile car un algorithme n'a pas toujours UNE complexité mais DES complexités (meilleur cas, cas moyen, pire cas, cas particuliers, etc.).

Commentaire de Patrice99 le 11/07/2006 14:04:10

Il faudrait inventer un concept prenant en compte la valeur de n associé à la complexité : par exemple, la charge de travail, en cycles CPU, ou bien en années-homme.

Commentaire de Patrice99 le 12/07/2006 08:49:59

> Existe-t-il donc un moyen de savoir que la complexité ne peut être inférieure à une certaine borne ?

Je crois que non, pas d'une manière générale : en fait j'ai cru comprendre qu'on classe les problèmes dans 4 catégories principales, suite à une analyse au cas par cas :
http://patrice.dargenton.free.fr/ia/vbbrainbox/index.html#_Toc39118564

Commentaire de Patrice99 le 22/07/2006 14:22:26

L'exemple est dans la doc du CLR Profiler !

www.microsoft.com/downloads/details.aspx?familyid=86ce6052-d7f4-4aeb-9b7a-94635beebdda&displaylang=en

    // Still recursive, but remembers previous results - much faster.
    static int Memo_Fibo(int i)
    {
        int result;

        if (!fibo_memo.FindResult(i, out result))
        {
            if (i <= 1)
                result = i;
            else
                result = Memo_Fibo(i-1) + Memo_Fibo(i-2);
        }

        // This call leaks memory,
        // because it always adds to the list.
        fibo_memo.Enter(i, result);      

        return result;
    }

You can simply look in a cache to determine whether you already computed Fibo with this argument. If so, you simply return the previous result; otherwise, you compute it. And of course, if you compute it, you enter it into the cache.
The following example shows how the cache works. It is nothing fancy – a linear list, with ways to search and enter new information.

    // List to remember association of previous arguments and results.
    class ListEntry
    {
        int argument;
        int result;
        ListEntry next;

        public ListEntry(int argument, int result, ListEntry next)
        {
            this.argument = argument;
            this.result = result;
            this.next = next;
        }

        public bool FindResult(int argument, out int result)
        {
            if (this.argument == argument)
            {
                result = this.result;
                return true;
            }
            else if (next != null)
            {
                return next.FindResult(argument, out result);
            }
            else
            {
                result = 0;
                return false;
            }
        }
    }

    ListEntry memoList;

    public Memo()
    {
        memoList = null;
    }

    void Enter(int argument, int result)
    {
        memoList = new ListEntry(argument, result, memoList);
    }

    bool FindResult(int argument, out int result)
    {
        if (memoList != null)
        {
            return memoList.FindResult(argument, out result);
        }
        else
        {
            result = 0;
            return false;
        }
    }

Commentaire de Cacophrene le 23/07/2006 13:01:11

Salut !

N'allons pas trop vite. Ecrire que l'application directe de la formule de Binet (message de us_30 ci-dessus, en rapport avec une source déjà postée sur VBFrance) donne une complexité constante, c'est séduisant, certes, mais faux. N'oublions pas que l'écriture "^ N" cache un calcul de puissance, donc au moins une complexité logarithmique (si la fonction interne de VB est une exponentiation rapide)... car la "puissance" (ou exponentiation pour faire jargonneux) n'est pas une opération élémentaire. Si Binet donnait Fibonacci en un nombre constant d'opérations élémentaires... tous les algorithmes seraient idiots. Pourquoi ? Parce que cela voudrait dire qu'il suffirait de demander Binet(10^(10^10)) pour avoir IMMEDIATEMENT Fibo(10^(10^10)) ! Prudence donc.

Cordialement,
Cacophrène

Commentaire de Cacophrene le 24/07/2006 13:04:16

Salut !

Merci pour ton code Patrice99. Je m'en suis inspiré (sans le suivre vraiment à la lettre, car ma compréhension du C++ n'est que partielle... et plutôt par déduction/analogie que par pratique) pour rédiger un algorithme 1' faisant suite au premier dont il dérive. Evidemment, pour les performances, il n'y aucune comparaison possible.

Cordialement,
Cacophrène

Commentaire de Cacophrene le 24/07/2006 19:33:59

Salut !

La complexité est plus faible 1. pour une raison intuitive (l'algorithme est sensiblement plus rapide que son équivalent sans sauvegarde des résultats intermédiaires) et 2. pour une raison logique (le nombre d'opérations élémentaires (additions surtout) a fortement diminué puisque nous ne refaisons pas les calculs déjà effectués). En fait, il ne reste plus qu'à mettre un nom sur cette complexité. Avis aux amateurs :-D

Cordialement,
Cacophrène

Commentaire de Patrice99 le 27/07/2006 15:59:21

Ok, la programmation à l'air vraiment simple et efficace, juste deux remarques : le QueryPerformanceCounter n'a pas l'air de marcher sur ma machine (j'ai des temps négatifs !), et Global peut être remplacé par Private Values() As Long

Commentaire de Cacophrene le 28/07/2006 08:45:20

Salut !

@Patrice:
Je ne vois pas comment tu peux obtenir des résultats négatifs. Je n'ai jamais été confronté à ce problème. Si tu as d'autres infos, je suis preneur.

@us_30:
D'accord pour le côté pratique. On tire profit des types (de leur précision) et des conversions. Heureux bricolage, diront certains.

Cordialement,
Cacophrène

Commentaire de jean_marc_n2 le 28/07/2006 17:58:26

Hello,

Non ce n'est pas la version de Windows, car cette API fonctionne bien avec Windows XP Edition Familiale (SP1 & SP2). En revanche, ca pourrait être lié au hardware de la machine (cf. http://channel9.msdn.com/ShowPost.aspx?PostID=156175)

De plus, MSDN précise bien dans la doc de cette API : "... bla bla SI VOTRE SYSTEME EST EQUIPE DUN COMPTEUR HAUTE PERFORMANCES bla bla bla ..."

La machine sur laquelle tu as un souci serait elle un Atlhon?

Commentaire de Cacophrene le 29/07/2006 07:44:13

Salut !

Un problème de matériel... ce n'est pas drôle ça ! Au pire, il est toujours possible de se rabattre sur GetTickCount. On obtiendra des mesures moins précises, mais faute de mieux c'est encore raisonnable.

Cordialement,
Cacophrène