/* formule.js
   (C) 2005 Jean-Paul Davalan
 */
var Fib=new Array(0,1,1,2,3,5,8,13,21,34,55,89,144);

function fib(n) {
  if(Fib[n] == null) {
    var a = Math.floor(n/2), b=n-a;
    Fib[n] = fib(a+1)*fib(b) + fib(a)*fib(b-1);
  }
  return Fib[n];
}

function gcd(a, b) {
   var u=Math.abs(parseInt(a)), v=Math.abs(parseInt(b));
   while(v!=0) {
     w = u%v;
     u=v;
     v=w;
   }
   return u;
}

function formule() {
  this.t  = new Array();
  this.t1 = new Array();
  this.t2 = new Array();
  this.cf = new Array();
  this.maxi = 3;
  this.solution = null;
  
  function lit(s) {
    var tab = s.split(/\,/g);
    var currt=0;
    for(var i=0;i<tab.length;i++) {
      var u;
      if(tab[i]==null) continue;
      if(tab[i]=="") tab[i]="n";
      do {
        u=tab[i];
        tab[i] = tab[i].replace(/\s+/,"");
        tab[i]=tab[i].replace(/[a-zA-Z_]+/g,"");
      }while(u!=tab[i]);
      if(tab[i]==null) continue;
      if(tab[i]==""||tab[i]=="+"||tab[i]=="-") tab[i]="0";
      tab[i] = parseInt(tab[i]);
      
      var test=true;
      for(var j=0;test && j<currt;j++) {
         if(this.t[j]==tab[i]) test = false;
      }
      if(test) {
        this.t[currt]=tab[i];
        currt++;
      }
    }
    for(var i=0;i<this.t.length-1;i++) {
      for(var j=i+1;j<this.t.length;j++) {
        if(this.t[i] < this.t[j]) {
          var a = this.t[j];
          this.t[j] = this.t[i];
          this.t[i] = a;
        }
      }
    }
    //alert(this.t);
    var v=this.t[this.t.length -1];
    for(var i=0;i<this.t.length;i++) {
      this.t1[i] = this.t[i]-v;
    }
    //alert(this.t[0]);
    for(var i=0; i < this.t.length;i++)
      this.t2[i]=0;
  }
  this.lit=lit;

/* on a plusieurs indices, par exemple n+35 n+21 n+17 n+12 n+5 qui sont placés 
      dans le tableau t sous la forme des nombres 35 21 17 12 5
      et dans t1 sous la forme 30 16 12 7 0 (le dernier est nul)
      Il s'agit de trouver une relation a*Fn+30 + b*Fn+16 + c*Fn+12 + d*Fn+7 + e*Fn
      or  F(n+30) = F(31)*F(n)+F(30)F(n-1)
          F(n+16) = F(17)*F(n)+F(16)F(n-1)
          F(n+12) = F(13)*F(n)+F(12)F(n-1)
          F(n+7)  = F(8)*F(n) +F(7)F(n-1)
      il suffit donc de déterminer a, b, c, d tels que aF(30)+bF(16)+cF(12)+dF(7) = 0
      et de prendre e = -(aF(31)+bF(17)+cF(13)+dF(8));
      ce qui ne doit pas être très difficile

      1er cas 
      -------
      on a seulement trois termes F(n+k), F(n+s) et F(n)
      F(n+k) = F(k+1)*F(n)+F(k)F(n-1)  on multiplie par F(s)
      F(n+s) = F(s+1)*F(n)+F(s)F(n-1)  on multiplie par -F(k) et on ajoute
      F(s)*F(n+k) - F(k)*F(n+s) =(F(s)*F(k+1) - F(s+1)*F(k)) * F(n)
     
      F(s)*F(n+k) - F(k)*F(n+s) - (F(s)*F(k+1) - F(s+1)*F(k)) * F(n) = 0

      autres cas
      ----------
      on a au moins quatre termes (dont F(n))
      les coeff à trouver sont a0 a1 a2 a3 ... ap-2 ap-1 ap
      on choisit a0 a1 a2 a3 ... ap-2 au hasard 
      on calcule a0*F(k0) + a1*F(k1) + ....ap-2 * F(kp-2)
      on détermine ensuite ap-1 pour une somme nulle 
      a0*F(k0) + a1*F(k1) + .... ap-2 * F(kp-2) + ap-1 * F(kp-1) = 0
      on termine en calculant 
      a0*F(k0+1) + a1*F(k1+1) + ....ap-2 * F(kp-2+1)+ap-1 * F(kp-1+1)

      variante
      --------
      on détermine à l'aide du 1er cas autant de formules entre l'un des premiers termes F(n+k)
      et les deux derniers F(n+s) et F(n)
      
       a0 F(n+k0) + b0 F(n+s) + c0 F(n) = 0
       a1 F(n+k1) + b1 F(n+s) + c1 F(n) = 0

       ar F(n+kr) + br F(n+s) + cr F(n) = 0 et on additionne pour obtenir

       a0*F(n+k0)+a1*F(n+k1)+...+ar*F(n+kr)+(b0+b1+...+br)*F(n+s) + (c0+c1+...+cr)*F(n) = 0

*/
    
   function coefs(t, z) {
       var n = this.t1.length;
       
       var k = this.t1[t], s = this.t1[n-2], c=this.t1[n-1];
       var u = fib(s), v=-fib(k), w = fib(s+1)*fib(k)-fib(s)*fib(k+1);
       u *=z; v*=z; w *=z;
       this.t2[t]=u;
       this.t2[n-2] += v;
       this.t2[n-1] += w;
   }
   this.coefs=coefs;
      
   function solve() {
      var n = this.t1.length;
      var m;
      for(var i=0; i<n;i++) {
        this.t2[i]=0;
      }
      for(var i=0; i<n-2;i++) {
        if(i==0) m=1
        else {
          m=Math.floor(2*this.maxi*Math.random());
          if(m>=0) m = m+1;
        }
        this.coefs(i,m);
      }
      var s="";
      var g = this.t2[0];
      for(i=1;i<n;i++) {
        if(this.t2[i]!=0) g = gcd(g, this.t2[i]);
      }
      for(var i=0;i<n;i++) {
         this.t2[i] /= g;
      }
      for(var i=0;i<n;i++) {
        var a = this.t2[i];
        if(i==0) { 
           if(a!=1) s += a+"*";
          
        } else if(a>0) {
           if(a != 1)
              s += " + "+a+"*";
           else 
              s += " + ";
        } else {
          if(a ==-1)
            s += " - ";
          else
            s += " - "+(-a)+"*";
        }
        
        if (a!=0) s +="F(n";
       
        var b = this.t[i];
        if(b>0) s+= "+"+b;
        else if(b<0) s +=b;
        s += ")";
      }
      s += " = 0";
      this.solution = s;
      return s;
   }
   this.solve=solve;
}

function cherche() {
  var m=new formule();
  var s = document.frm.a.value.split(/# \-{30}/g);
  do {
     u=s[0];
     s[0] = s[0].replace(/[\n\s]+$/,"")
  }while(u != s[0]);
  m.lit(s[0]);
  var s1 = m.solve();
  var u= s[0]+"\n# -------------------------------------\n"+
         "relation entre nombres de Fibonacci :\n\n";
  document.frm.a.value = u+s1;
}

function multi(k) {
  var fml="";
  var k1 = parseInt(k);
  for(var i=0;i<k1;i++) {
    fml += formalea();
    fml +=";\n\n";
  }
  document.frm.a.value = "Fn+8 , Fn+4 , Fn+2 , Fn, Fn-3\n"+
                         "# -------------------------------------\n"+
           "relations entre nombres de Fibonacci :\n\n" +
           fml;
}

function textalea() {
      var n=4+Math.floor(8*Math.random());
      var s="";
      var d=Math.floor(8*Math.random());
      for(var j=0; j<n; j++) {
        var p=Math.floor(15*Math.random())-d;
        if(j>0) s +=", ";
        s += "Fn";
        if(p>=0)
        s += "+"+p;
        else
        s += "-"+(-p);
      }
      return s;
}

function formalea() {
    var s1="";
    do {
      var s = textalea();
      var m=new formule();
      m.lit(s);
      if(m.t2.length>=3) {
        s1=m.solve();
      }
    } while(s1=="");
    return s1;
}

function alea() {
  document.frm.a.value =  textalea();
}