#include <iostream>
#include <cmath>
using namespace std;
/*
Ce deuxième chapitre va démontrer l'impact de la complexité d'un algorithme
grâce à un exemple, la suite de fibonacci.

Cette suite est défini par :
 F(0)=1
 F(1)=1
 puis F(n)=F(n-1)+F(n-2)

Nous allons essayer de programmer des fonctions qui nous donne la valeur d'un
terme de la suite.

La première méthode qui nous vient à l'esprit est celle qui se contente d'appliquer
par récurence la définition de la suite. Cette méthode est très mauvaise, car on
voit qu'il est nécessaire de faire un très grand nombre d'appel à la fonction pour
avoir la réponse puiceque le résultat totale est augmenté par pas de 1.

On peut démontrer qu'il existe un entier K tel que pour calculer fibo1(n) le temps
sera K*phi^(n) ou phi est une constante que je définirait plus bas.
On dit que la complexité de l'algorithme est en O(phi^n)

*/
int fibo1(int n)
{
  if (n<2)
    return 1;
  else
    return fibo1(n-1)+fibo1(n-2);
}

/*

Le problème de la fonction précédente vient de ce qu'elle calcule plusieurs fois
chaque F(n) car elle ne les enregistre pas. Une deuxième méthode possible est de
partir de F(0) puis de monter vers F(n) en enregistrant à chaque fois 2 indices
pour pouvoir calculer le suivant. Cette méthode utilise juste une boucle qui fera
autant d'itération que n.
Si une boucle mets un temps K pour s'exécuter, alors la fonction mettra un temps
K*n pour s'exécuter intégralement. La complexité de la fonction est donc en O(n)
ce qui est bien mieux que O(phi^n) que l'on avait tout à l'heure car phi^n croit
beaucoup plus vite que n.

*/
int fibo2(int n)
{
  int i;
  int f0=1,f1=1;

  for (i=2;i<=n;i++)
  {
    f1=f0+f1;
    f0=f1-f0;
  } 
  return f1;
}



/*

On peut démontrer par récurrence la formule :
F(n+p) = F(n)*F(p) + F(n-1)*F(p-1)
La démonstration est hors de notre sujet, mais pas extrémement compliquée.

On peut appliquer cette formule pour avoir :
F(2n) = F(n)^2 + F(n-1)^2
F(2n+1) = F(n) * (F(n) + 2*F(n-1))

et on peut appliquer ces formule par récurence pour obtenir une fonction
bien plus rapide qui va s'appuyer sur notre découverte précédente, à
savoir, celle de calculer d'un coup deux indices successif pour économiser
du temps de calcul.

Cette méthode est bien meilleur, mais avec la limite de taille imposé sur les
entier par le C++ on ne peut pas voir de différence signifitive entre fibo2
et fibo3.

Pour s'exécuter la fonction va s'appeler par récurence en calculant d'abord le
terme F(n) qui aura besoin de F(n/2) qui aura besoin de F(n/4) etc.
Jusqu'à ce que n/(2^x)=1 un simple calcul nous montre que x=log2(n) (le logarithme
en base 2 de n). Ceci veut dire qu'il y aura log2(n) appel à la fonction pour
le calcul. Et donc si un appel à fibo3_inside prend un temps K, le tout prendra
un temps K*log2(n), donc la complexité est en O(log2(n)) ce qui est encore mieux
que tout à l'heure car n croit plus vite que log2(n).

*/

//C'est cette structure qui permet de renvoyer deux indices d'un coup.
struct fibo
{
  fibo(int A,int B) {a=A;b=B;};
  int a,b;
};

fibo fibo3_inside(int n)
{
  if (n<=1)
    return fibo(1,1);
  else
  {
    fibo p=fibo3_inside(n/2);
    if (n&1)
      return fibo(p.a*(p.a+2*p.b),p.a*p.a+p.b*p.b);
    else
      return fibo(p.a*p.a+p.b*p.b,p.b*(2*p.a-p.b));
  }
}
int fibo3(int n)
{
  return fibo3_inside(n).a;
}
/*

La méthode qui suit est aussi en O(log2(n)) mais elle est plus simple à
comprendre. De plus elle fait appel au produit matriciel, ce qui met un peu
de diversité par ici.

Car il ne faut pas oublier qu'un algorithme recherche la rapidité, mais si
un gain extrêmement faible en vitesse doit être fait au mépris de la lisibilité
de l'algorithme, il vaut souvent mieux préférer une fonction un peu plus lentes
plus compréhensible, car quand vous aurez besoin de reprendre votre algorithme
plus tard, vous serez bien embêtez si vous ne pouvez même plus le comprendre.

Nous utilisons là une propriété de ce produit matriciel :
( 1  1 )   ( F(n-1) )   ( F(n-1) + F(n-2) )   (  F(n)  )
(      ) * (        ) = (                 ) = (        )
( 1  0 )   ( F(n-2) )   (     F(n-1)      )   ( F(n-1) )

on en déduit :
(  F(n)  )   ( 1  1 ) ^n-1   ( 1 )
(        ) = (      )      * (   )
( F(n-1) )   ( 1  0 )        ( 1 )

Le problème se résume donc à l'élévation d'une matrice à une puissance donnée,
ce que nous ferons par un algorithme "diviser pour regner". Nous verrons dans un
chapitre ultérieur ce que cela signifie.
Ceux qui ont fait des math me demanderont pourquoi ne pas diagonaliser la matrice,
je leur répondrait que c'est ce que je ferait juste après.

*/

//Une structure de matrice carré de taille 4 avec une multiplication par une
//autre matrice ou par un vecteur.
struct mat
{
  mat(int A,int B,int C,int D) {a=A;b=B;c=C;d=D;}
  int a,b,c,d;
  mat operator*(mat &autre) {return mat(a*autre.a+b*autre.c,a*autre.b+b*autre.d,c*autre.a+d*autre.c,c*autre.b+d*autre.d);}
  fibo operator*(fibo &autre) {return fibo(a*autre.a+b*autre.b,c*autre.a+d*autre.b);}
};

//Cette fonction élève la matrice m à la puissance n.
//Nous reviendrons sur cette méthode plus tard.
mat mat_power(mat m,int n)
{
  if (n<=1)
    return m;
  else
  {
    if (n&1)
      return mat_power(m*m,n/2)*m;
    else
      return mat_power(m*m,n/2);
  }
}
int fibo4(int n)
{
  fibo t=mat_power(mat(1,1,1,0),n-1)*fibo(1,1);
  return t.a;
}

/*

Les deux dernières méthodes font appel à l'étude mathématique de la suite.
Elles ont l'immense avantage d'être en O(1) c'est à dire que le temps de
calcul est constant et ne dépend pas de n.
Malheureusement elles perdent en précision se qu'elles gagnent en vitesse,
mais donnent néanmoins un très bon ordre de grandeur de F(n).

Tout le monde a déjà entendu parler de Phi, le nombre d'or.
on définit Phi par :
    1 + 5^(1/2)
phi=-----------=1.618
         2
Ce nombre qui est le rapport de la hauteur sur la largueur d'un rectangle
parfait, est intimement lié à la suite de Fibonacci. Par exemple en divisant
F(n) par F(n-1) on en obtient une approximation d'autant meilleure que n est
grand.
L'étude mathématique de la suite de fibonacci (que nous ne ferons pas ici)
nous apprend que :
           1
F(n) = --------- * (phi^(n+2) + (-1)^n * phi^(-n))
       1 + phi^2

En réalité on peut justement trouver ce résultat en diagonalisant la matrice
que nous avons utilisée tout à l'heure.

La fonction suivante est juste une mise en application de la formule ci-dessus.
*/

#define phi 1.6180339887498948482f       //phi=(1+sqrt(5))/2
#define inv 0.27639320225002103036      //inv=1/(phi^2+1)
double fibo5(int n)
{
  double a,b;
  a=pow(phi,n+2);
  b=pow(phi,-n)*pow(-1.0,n);
  return inv*(a+b);
}

/*

On remarque que le terme en phi^(-n) est rapidement très petit, et à partir de
n=2 on peut le négliger car il est inférieur à 1/2 et F(n) est l'entier le
plus proche de la valeur :
phi^(n+2)
---------
1+phi^(2)

La méthode qui suit est donc "parfaite" (au imprécisions du calcul près), et
c'est la dernière qui le soit. Elle est encore un peu plus rapide car elle fait
mois de calcul que fibo5.

*/
double fibo6(int n)
{
  double f=inv*pow(phi,n+2);
  return (f<2e10)?int(f):f;
}



void main()
{
  int n;
  cout << "Entrez 0 pour quitter." << endl << endl;
  do
  {
    cout << "n ? ";
    cin >> n;
    if (n<36) cout <<"fibo1 : " << fibo1(n) << endl;
    if (n<46) cout <<"fibo2 : " << fibo2(n) << endl;
    if (n<46) cout <<"fibo3 : " << fibo3(n) << endl;
    if (n<46) cout <<"fibo4 : " << fibo4(n) << endl;
    if (n<81) cout <<"fibo5 : " << fibo5(n) << endl;
    if (n<81) cout <<"fibo6 : " << fibo6(n) << endl;
  }while(n!=0);
}

/*
Si vous essayer sur des nombres comme n=35 vous verrez à quel point la première
méthode est déjà beaucoup plus lente que les autres, ce qui vous donne un petit
apercu de ce qu'il se passerait si on pouvait gérer des nombres plus grand et
que l'on faisait le calcul plus loin.

En conclusion, on dira qu'un bonne algorithme se doit d'être en O(n) ou au pire
en O(n*log(n)). Mais qu'un algorithme en O(n^2) voire pire O(exp(n)) ou certaine
atrocité comme O(n!) sont absolument inéficace car inadapté à un nombre important
(ou pas tellement) de donnée.
Les meilleurs algorithme sont souvent en O(log(n)) mais tout les problèmes ne
peuvent pas se résoudre avec des algorithmes aussi rapides.
Ceux qui ont des solution en O(1) c'est à dire en tant constant, sont souvent
qualifié de triviaux.
*/