/* Resolution systeme d'equations lineaire      */
/* par methode de Gauss                         */
/* Evaluation du temps d'execution              */  

public class TestSystemeEquationsLineaires {

/* Fonction de creation d'un tableau de double  */
/* initialisee avec des nombres aleatoires      */
/* entiers compris dans l'intervalle [0.0,max]  */

  static double [] initRandTableau(int taille,double max) {
    double [] tab = new double[taille];
    for ( int i = 0 ; i < taille ; i++ ) {
      tab[i] = Math.random()*max; }
    return tab;
  }

/* Fonction de creation d'une matrice de double */
/* initialisee avec des nombres aleatoires      */
/* entiers compris dans l'intervalle [0.0,max]  */

  static double [][] initRandMatrice(int taille,double max) {
    double [][] tab = new double[taille][taille];
    for ( int i = 0 ; i < taille ; i++ ) {
      for ( int j = 0 ; j < taille ; j++ ) {
        tab[i][j] = Math.random()*max; } }
     return tab;
  }
  
/* Fonction de calcul du produit d'un tableau  */
/* carre de taille n.n par un tableau          */
/* a 1 indice de taille n                      */
/* Resultat: Un tableau a 1 indice de taille n */

  static double [] produitMatriceVecteur(double [][] m,
                                         double [] v) {
    int n = v.length;
    double [] w = new double[n];
    for ( int i = 0 ; i < n ; i++ ) {
      w[i] = 0.0;
      for ( int j = 0 ; j < n ; j++ ) {
        w[i] = w[i] + m[i][j]*v[j]; } }
    return w;
  }

/////////////////////////////////////////////////

/* Fonction de clonage d'un tableau de double  */
/* a 1 indice                                  */

  static double [] clone(double [] t) {
    int n = t.length;
    double [] nt = new double[n];
    for ( int i = 0 ; i < n ; i++ ) {
      nt[i] = t[i]; }
    return nt;
  }

/* Fonction de clonage d'un tableau de double  */
/* a 2 indices                                 */

  static double [][] clone(double [][] t) {
    int n = t.length;
    int m = t[0].length;
    double [][] nt = new double[n][m];
    for ( int i = 0 ; i < n ; i++ ) {
      for ( int j = 0 ; j < m ; j++ ) {
        nt[i][j] = t[i][j]; } }
    return nt;
  }

/* Permutation de Gauss                        */

  static void permutation(int l,double [][] m,double [] v) {
    int ll = l;
    int n = v.length;
    while ( m[ll][l] == 0.0 ) {
      ll++; }
    for ( int i = l ; i < n ; i++ ) {
      double [] tAux = m[l];
      m[l] = m[ll];
      m[ll] = tAux; }
    double aux = v[l];
    v[l] = v[ll];
    v[ll] = aux;
  }

/* Transformation de Gauss                     */

  static void transformation(double [][] m,double [] v) {
    int n = v.length;
    for ( int i = 1 ; i < n ; i++ ) {
      if ( m[i-1][i-1] == 0.0 )
        permutation(i-1,m,v);
      for ( int j = i ; j < n ; j++ ) {
        double facteur = m[j][i-1]/m[i-1][i-1];
        for ( int k = i-1 ; k < n ; k++ ) {
          m[j][k] -= m[i-1][k]*facteur; }
        v[j] -= v[i-1]*facteur;  } }
  }

/* Extraction de Gauss                         */
  
  static void extraction(double [][] a,double [] b,double [] v) {
    int n = b.length;
    v[n-1] = b[n-1]/a[n-1][n-1];
    for ( int i = n-2 ; i >= 0 ; i-- ) {
      v[i] = b[i];
      for ( int j = n-1 ; j > i ; j-- ) {
        v[i] -= v[j]*a[i][j]; }
      v[i] /= a[i][i]; }
  }
      
/* Resolution de Gauss                         */

  static void resolution(double [][] a,double [] b,double [] v) {
    transformation(a,b);
    extraction(a,b,v);
  }
  
/* Resolution de Gauss                         */
/* sur une copie des 2 tableaux en parametres  */

  static void resolutionGauss(double [][] a,double [] b,double [] v) {
    resolution(clone(a),clone(b),v);
  }

  static void testsRapiditeResolutionSystemeEquationsLineaires(int temps,int ni,int nf,int inc) {
    Ecran.formater("%6s%12s%14s%22s%14s\n","Taille","Appels","Temps total","Temps moyen","o(n^3)");
    for ( int nu = ni ; nu <= nf ; nu = nu+inc ) {
      double [][] m = initRandMatrice(nu,1.0);
      double [] v1 = initRandTableau(nu,1.0);
      double [] b1 = produitMatriceVecteur(m,v1);
      double [] v2 = initRandTableau(nu,1.0);
      double [] b2 = produitMatriceVecteur(m,v2);
      double [] v = new double[nu];
      Utilitaires.Minuteur minuteur = new Utilitaires.Minuteur();
      minuteur.temps = temps*1000;
      int i = 0;
      minuteur.lancement();
      long ti = System.nanoTime();
      do {
        if ( i%2 == 0 )
          resolutionGauss(m,b1,v);
          else
          resolutionGauss(m,b2,v);
        i++; }
      while ( minuteur.enCours );
      long t = System.nanoTime()-ti;
      Ecran.formater("%6d%12d%14d%22.3f%14.4f\n",nu,i,t,(double) t/i,(double) t/(double) i/((double) nu*nu*nu)); }
  }

/////////////////////////////////////////////////
  
/* Programme principal                         */

  public static void main(String [] args) {
    Ecran.afficher("Nombre de secondes de test? ");
    int temps = Clavier.saisirInt();
    Ecran.afficher("Niveau initial?   ");
    int ni = Clavier.saisirInt();
    Ecran.afficher("Niveau de fin ?   ");
    int nf = Clavier.saisirInt();
    Ecran.afficher("Increment     ?   ");
    int inc = Clavier.saisirInt();
    testsRapiditeResolutionSystemeEquationsLineaires(temps,ni,nf,inc);
  }
}