/* -----------------------------------------------------------------
   lfib.js Calcul (rapide) du nombre de Fibonacci 
   en utilisant F(n)=F(k+2)*F(n-k-1)+F(k+1)*F(n-k-2)
   avec n-k-1 multiple d'une constante. 
   (C) Jean-Paul Davalan 2005 <jpdvl@wanadoo.fr

   L'application javascript utilise la propriété : 
   Pour 0<= k<= n-2, F(n)=F(k+2)*F(n-k-1)+F(k+1)*F(n-k-2) 
   qui permet de ne calculer qu'une faible partie des nombres de Fibonacci 
   qui précèdent F(n). 
   En prenant k+1=50, seuls sont calculés deux nombres de Fibonacci 
   consécutifs toutes les 50 positions. Le programme est très simple à 
   écrire et est environ 25 fois plus rapide qu'en utilisant F(n)=F(n-1)+F(n-2). 
   Pour concevoir des algorithmes encore plus rapides pour de très 
   grandes valeurs de n, consulter par exemple ma page de liens sur les algorithmes.
  */
// ---------- Initialisations ---------------------------------------
/* Calcul d'une cinquantaine de nb de fibonacci :
   tableau  tf[i][c] des multiples par c=0, 1, 2, ... 9 des nombres
   de Fibonacci jusqu'à i=51 */
var fnum=50,
    lf=new Array(0,1,1,2), // début du tableau des Fibonacci
    tf=new Array();
for(var i=4;i<=fnum+2;i++) 
    lf[i]=lf[i-1]+lf[i-2];
var alp="0123456789"; // chiffres
for(var i=0;i<=fnum+1;i++) 
    tf[i] = new Array();
for(var j=0;j<10;j++) {
  c=alp.charAt(j);
  for(var i=0;i<=fnum+1;i++) 
    tf[i][c]=lf[i]*j;
}

// ---------- Fonction Fibonacci F(n) -------------------------------
/*   0 <= k <= n-2  F(n) = F(k+2)*F(n-k-1) + F(k+1)F(n-k-2)
   lfib(n) calcule Fibonacci(n). 
   Chaque valeur calculée est placée dans le tableau lf[n]
   pour éviter d'être recalculée plus tard
   tableau :  lf[n]
   fonction : lfib(n)       et lfib(n)=lf[n]
*/
function lfib(n){
  if(lf[n]!=null) return lf[n]; // pas de recalcul
  var k=n%fnum; // k est un multiple de fnum = 50
  // récursivité
  var u = ""+lfib(n-k-1), v = ""+lfib(n-k-2),r=0;
  var i=u.length-1, j=v.length-1; // positions des chiffres de droite
  var s="";
  // parcours de tous les chiffres de droite à gauche
  // tant qu'ils existent (0 sinon) ou que le reste n'est pas nul
  while(i>=0 || j>=0 || r!=0) {
    var x=(i<0)?0: tf[k+2][u.charAt(i)],
        y=(j<0)?0:tf[k+1][v.charAt(j)], 
        z = x+y+r, c = z%10;
    s = c+s;
    r=(z-c)/10;
    i--; j--;
  }
  lf[n]=s;
  return s;
}
// ---------- Gestion ------------------------------------------------
var  lf_current=500;    // le dernier n calculé
function lf_calcule() {
  var n = parseInt(document.grandfib.n.value);
  lf_current = n;
  var s = ""+lfib(n), s1="\nNb chiffres de Fib("+n+")= "+s.length;
  document.grandfib.ar.value=lf_cut(70,s)+s1;
}
/* coupe s en tranches de k chiffres pour l'affichage */
function lf_cut(k,s) {
  var s2="";
  for(var i=0;i<s.length;i+=k) {
    var u = s.substr(i,k);
    s2 +=u+"\n";
  }
  return s2;
}
function lf_suivant(m) { // passe de lf_current à lf_current+m
  lf_current += m;  // positif ou négatif
  if(lf_current<0) lf_current=0;
  document.grandfib.n.value=lf_current;
  lf_calcule();
}
function lf_efface() {
  with(document.grandfib) {
    ar.value="";n.value="";
  }
}
// ---------- Fin ------------------------------------------------------