FIBONACCI EN O( N )

Commentaire de MetalDwarf le 24/07/2004 11:28:05

Oui je connais cette methode je l ai eu en DS d'info. C'est d'ailleurs etonnant que l algorithme "naturel" soit exponentiel, que le plus reflechi en O(n) et  celui-la en O(log(n)). Ce qui est egalement troublant c est le fait que cette formule n ai pas de rapport a priori avec la suite de fibonacci (meme si demontrer la correction de cet algorithme n est pas dur du tout).

Commentaire de MetalDwarf le 24/07/2004 11:51:50

A oui c est vrai, je n avais pas regarde bien en detail ton code source.
Si tu veux que ton algo soit vraiment en O(log(n)), il faut imperativement utiliser l'algorithme d'exponentiation rapide sinon tu restes en O(n).
Il est tres simple a implementer, et il est naturellement recursif.

int exp_rap(int a, int n)
{
   int tmp;
   if(n=1) return 1;
   if(n%2)   // n impair
   {
       tmp = exp_rap(a,n/2);
       return (tmp*tmp)*a;
   }
    // n pair
   tmp = exp_rap(a,n/2);
    return tmp*tmp;
}

Bien sur vu que tu utilises des matrices il faut remplacer * par le produit des matrices.

Commentaire de Xs le 24/07/2004 14:38:35

Si, lim (n->+oo) (Un+2 = Un+Un+1) = (1+Rac(5))/2

D'ailleurs, une manniere assez rapide le n-ieme terme de la suite de fibonacci est :

(si on part de U0 en 1er terme et non pas U1)

Un+1 = 1/Rac(5) * (L^n + L_barre^n)

ou L est la limite, donc (1+Rac(5))/2 et L_Barre le conjugué ((1-Rac(5)/2).

C'est, je pense, assez rapide (plus rapide que cet algo je pense), puisque n est naturel

Commentaire de Xs le 24/07/2004 14:57:16

Tu comprends pas quoi ? Dis moi que j'essaie de t'expliquer :D

Commentaire de Xs le 24/07/2004 16:06:57

Re !

"Comment cette suite se fait elle ?"
=> Reformule ta question stp, je ne comprend pas trés bien ce qu'elle veut dire. Si tu demandes d'ou on la sort, faut voir pour la petite histoire des lapins de F.

Si tu parles de "comment calculer Un" :

Une suite est en faite une fonction adaptée pour N (donc l'application U:N->R alors qu'une fct est f:R->R ou dans le genre)
C'est a dire que (Un) est le n-ieme terme de la suite, et que n est un entier naturel (0,1,2,....)

Dans le cas de F., si on te donne U(0) = 0 et U(1) = 1, pour calculer
U(2) tu fais, sachant que U(n+2) = U(n) + U(n+1)
n+2 = 2 <=> n = 0

donc

U(0+2) = U(0) + U(0+1)
<=> U(2) = U(0) + U(1)
<=> U(2) = 0 + 1
<=> U(2) = 1

U(3) = U(1) + U(2)
<=> U(3) = 1 + 1
<=> U(3) = 2

U(4) = U(2) + U(3)
<=> U(4) = 1 + 2 = 3

etc.... (u(5) = 5 ; u(6) = 8 ; u(7) = 13....)

Mes variables, je suppose L et L_barre sont juste des lettres que j'ai prises pour remplacer ce nombre d'or dont l'ecriture dans une equation en ANSII est assez casse pieds et encore plus à lire.

L_barre est le conjugué de ce nombre. Le conjugué de a+b est a-b. donc L_barre = (1-Rac(5))/2.

Pour ma "formule", c'est mon prof de maths qui me l'a donné, sans la démontrer (enfin si, mais j'ai rien compris à ses histoires d'espaces vectoriel, linéarité,etc...)

Ah ui, L est la limite de la suite de F. C'est a dire que plus "n" devient grand, plus on prend n aussi grand que l'on veut, plus U(n) aura des valeurs proches de 1.668.... ((1+Rac(5))/2)

Voici la démo (enfin.. les fractions continues ne sont pas une démo à mon gout mais bon)
http://www.sciences-en-ligne.com/momo/chronomath/anx3/suite_fibo.html

J'epere que tu auras compris ce que je t'ai expliqué... mais sache que faire plus précis va m'etre difficile car je ne suis qu'en TS (ex-1er S :D)


cordailement

Commentaire de coucou747 le 24/07/2004 16:55:25 administrateur CS

ah oui, c'est les lapins quse multiplient tout les 4 mois...
Qqn dans ma classe avait le nombre d'or comme thème d'étude...

Donc, cette "fonction" si j'ai bien compris, donne :
f(x)=f(x-1)+f(x-2)
et évidement, x ne peut pas être infèrieur a deux car avec un seul lapin, on a rien...
Mais ceci c'est une fonction f:N->N
et ça ne va pas vers le nombre d'or...

Commentaire de coucou747 le 24/07/2004 21:01:46 administrateur CS

je ne compredns pas vraiment ce que tu veux faire, mais si tu veux, j'ai un truc qui permet de faire a=i^d%n
on s'en sert en cryptographie rsa

Commentaire de MetalDwarf le 25/07/2004 11:07:08

Ba je ne vois pas trop ou est le probleme!!
Est ce que tu as une fonction de multiplication des matrices 2x2. Si non tu peux facilement en faire une qui aurait comme prototype :

int [2][2] mult_mat(int mat1[2][2],int mat2[2][2]);

a partir de la ton algo devient :

int [2][2] exponentiation_rapide(int mat[2][2], int Puissance)
{
    int resultat[2][2] = {{1,0],{0,1}};  // la matrice unite
    while (Puissance != 0)
    {
        // si Puissance est impair :
        if(Puissance % 2)
            resultat = mult_mat(resultat,mat);
        mat = mult_mat(mat,mat);
        Puissance /= 2;
    }
    return resultat;
}

Je crois que c est correct, mais je ne guarantie rien car je n ai implemente cet algorithme qu en Caml (langage au programme en math sup).

Commentaire de Xs le 25/07/2004 13:32:05

Ah bon ? C'est la meilleure celle-là.

En C/C++, peut etre que tu ne peux pas retourner de tableau a 2 dim, mais en tout cas tu peux retourner un double ptr :

int**exponentiation_rapide(int mat[2][2], int Puissance)
{
    int **resultat // la matrice unite
    *resultat = new int[2]

for(int i=0;i<2;i++)
   resultat[i] = new int[2];

    while (Puissance != 0)
    {
        // si Puissance est impair :
        if(Puissance % 2)
            resultat = mult_mat(resultat,mat);
        mat = mult_mat(mat,mat);
        Puissance /= 2;
    }
    return resultat;
}

Commentaire de coucou747 le 26/07/2004 20:01:51 administrateur CS

euh...
si je comptrends bien ,ceci devrais fonctionner pour calculer cette suite ?

#include <stdio.h>
int main(void)
{
int unsigned long a,b,c,i=1;
a=0;
b=1;
i++
c=a+b;
printf("f(%i)=%d\n",i,c);
a=b;
b=c:
}

Commentaire de JCDjcd le 27/07/2004 10:59:59

Non la formule suivant, temps de calcul independant de n !! :

Un=1/sqrt(5) * [p0^n - p1^n]
avec p0 et p1 les deux nombres en or :
p0=(1+sqrt(5))/2
p1=(1-sqrt(5))/2

DEMONSTRATION DE LA FORMULE :
on suppose que Un est de la forme x^n (c'est exponentielle, donc ...) alors Un+2 = Un+1 + Un
Donc : x^(n+2) - x^(n+1) - x^n = 0     <=>   x^n * [x²-x-1] = 0
On suppose que x est non nul, donc x²-x-1=0
donc x=p0 ou x=p1 (nombres definis plus haut, les deux nombres en or).
De plus on peut rajouter un constant k devant x^n : Un = k.x^n
La demonstration est la meme. Mais on a aussi : U0=0 et U1=1, c'est deux conditions nous obligent a ecrire : Un = k0.p0^n + k1.p1^n    (qui est solution de Un+2 = Un+1 + Un, voir demonstration plus haut), il suffit donc de determiner k0 et k1 selon les deux valeurs initiales de U0 et U1.
U0 = 0 = k0 + k1   donc   k1 = -k0
U1 = 1 = k0.p0 + k1.p1  donc  k0(p0-p1)=1  donc k0=1/(p0-p1)
Or p0-p1=sqrt(5) , faite le calcul vous meme ...
D'ou la formule :

Un=1/sqrt(5) * [p0^n - p1^n]

ou sinon :

Un=1/sqrt(5) * [((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n]
1

Commentaire de JCDjcd le 27/07/2004 14:35:29

Ouais, si tu veux toutes la suite, il faut faire la boucle, mais si tu veux un nombre de la suite en particulier (sans calculer les precedents) alors ma methode (enfin c'est pas la mienne, mais celle que j'ai ecrite et demonstrée) est plus rapide.