Nombres de Fibonacci

Nombres de Fibonacci

Les nombres de Fibonacci sont définis par la récurrence :

On peut calculer la valeur du nombre de Fibonacci au rang n de plusieurs façons :

Programmation récursive

long fibonR( int n)
{
        if((n==0)||(n==1)) return 1;
        else return fibonR(n-1)+fibonR(n-2);
}

Le nombre d’appels récursifs au rang n est :

On montre par récurrence que

La récurrence qui exprime le nombre de Fibonnacci au rang n se résout de la façon suivante :

Soient et les racines de l’équation sont et , est le nombre d’or

on a

on a alors

donc et , le deuxième terme tend donc vers 0.

Le calcul de croît à peu près comme

Programmation itérative

long fibonI( int n)
{       int i=2;long F0=1, F1=1, F;
  while(i<=n)
  {
                F=F0+F1;
                F0=F1;
                F1=F;
                ++i;
  }
  return F1;
}

Le temps de calcul est clairement de l’ordre de n.

Peut-on faire mieux ?

Soit

alors on a :

On déduit que .

Nous nous proposons de calculer Mⁿ en faisant le moins possible de multiplications. L’algorithme classique effectue n multiplications. Pour en faire moins nous nous proposons de programmer l’algorithme suivant :

Supposons que n soit une puissance de 2. Le nombre de multiplications effectuées par cette méthode est donné par la récurrence :

Soit

Dans ce cas le temps de calcul de

est donc proportionnel à

class Matrice{
    long A, B, C, D;
  public :
    Matrice(long a, long b, long c, long d){
       A=a; B=b; C=c; D=d;
    } 
    Matrice operator *( Matrice m){
       long a, b, c, d;
       a = A*m.A+B*m.C;
       b = A*m.B+B*m.D;
       c = C*m.A+D*m.C;
       d = C*m.B+D*m.D;
       return  Matrice(a, b, c, d);
   }
}

Matrice xn( long n, Matrice m){
       long A, B, C, D, A1, B1, C1, D1;
       if(n==0)      return new Matrice(1, 0, 0, 1);
       else if(n==1) return new Matrice(m.A, m.B, m.C, m.D);
       else {
           long n2 = n/2;
           Matrice res = xn(n2, m*m);
           if(n%2!=0)res = m*res;
           return res;
       }
}

long fibonM(long n){
       Matrice m = new Matrice(0, 1, 1, 1 );
       return xn(n, m).D;
}

Ce résultat n’est qu’approximatif : en effet le calcul itératif effectue n additions, alors que le précédent algorithme effectue (si n est une puissance de 2) log₂(n)*8 multiplications et log₂(n)*4 additions. Les additions prennent un temps proportionnel à m (nombre de chiffres des nombres additionnés) alors que les multiplications prennent un temps proportionnel à n² ou un peu moins ( voir plus loin).

Exercices