maindpr.cpp

algorithme de multiplication suivant l algorithme de Strassen diviser pour regner pour exemplaire de

////////////////////////////////////////////////////////////////////////////////
///
/// @file mainDPR.cpp
///
/// @author Marwan et Mehdi
///
////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <string>
#include <fstream>
#include "matrice.h"

using namespace std;

//////////////////////////////////////////////////////////////////////////////////
///
/// Permet de faire la multiplication de deux matrices de meme taille par la methode 
/// conventionnelle
///
/// @param[in] a la premiere matrice
/// @param[in] b la deuxieme matrice
/// @param[in] taille la taille de la matrcie resultante qui doit supposer etre la 
///				meme que les matrices.
///
/// @return La matrice resultante de la multiplication
///
//////////////////////////////////////////////////////////////////////////////////
matrice conventionnelle(const matrice &a, const matrice &b, int taille)
{
  matrice c(taille);

  for(int i = 0; i < taille; i++)
    for(int j = 0; j < taille; j++)
    {
      c.mat[i][j] = 0;
      for(int k = 0; k < taille; k++)
      {
        c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
      }
    }
  return c;
}

//////////////////////////////////////////////////////////////////////////////////
///
/// Permet de faire la multiplication de deux matrices de meme taille par la methode 
/// de strassen
///
/// @param[in] a la premiere matrice
/// @param[in] b la deuxieme matrice
/// @param[in] taille la taille de la matrcie resultante qui doit supposer etre la 
///				meme que les matrices.
///
/// @return La matrice resultante de la multiplication
///
//////////////////////////////////////////////////////////////////////////////////
matrice strassen(matrice &a, matrice &b, int taille)
{
  matrice c(taille);

  // Pour le calcul de seuil, on change la valeur pour un multiple de 2 (par exemple: 4,16,32,64,128..)
  if(taille <= 2)
  {
	c = conventionnelle(a, b, taille);
	return c;
  } 

  taille /= 2;

  // preparation des quadrants a recuperer

  //quadrants de la matrice A
  matrice a11 = a.quadrant(1);
  matrice a12 = a.quadrant(2);
  matrice a21 = a.quadrant(3);
  matrice a22 = a.quadrant(4);

  //quadrants de la matrice B
  matrice b11 = b.quadrant(1);
  matrice b12 = b.quadrant(2);
  matrice b21 = b.quadrant(3);
  matrice b22 = b.quadrant(4);
  
  // calculs des sous-matrices pour le calcul de Strassen
  matrice A = a21 + a22 - a11;
  matrice B = b22 - b12 + b11;
  matrice m1 = strassen(A, B, taille);
  matrice m2 = strassen(a11, b11, taille);
  matrice m3 = strassen(a12, b21, taille);

  A = a11 - a21;
  B = b22 - b12;
  matrice m4 = strassen(A, B, taille);

  A = a21 + a22;
  B = b12 - b11;
  matrice m5 = strassen(A, B, taille);

  A = a12 - a21 + a11 - a22;
  matrice m6 = strassen(A, b22, taille);

  A = b11 + b22 - b12 - b21;
  matrice m7 = strassen(a22, A, taille);

  // Calcul des quadrants de la matrcie resultante
  matrice c11= m2+m3;
  matrice c12= m1+m2+m5+m6;
  matrice c21= m1+m2+m4-m7;
  matrice c22= m1+m2+m4+m5;

  // Assemblage des sous matrices en une matrice resultante
  for(int i = 0 ; i<taille ; i++)
  {
	  for(int j = 0 ; j<taille ; j++)
	  {
		  c.mat[i][j] = c11.mat[i][j];
		  c.mat[i+taille][j] = c21.mat[i][j];
		  c.mat[i][j+taille] = c12.mat[i][j];
		  c.mat[i+taille][j+taille] = c22.mat[i][j];
	  }
  }

  return c;
}

////////////////////////////////////////////////////////////////////////////////
///
/// Programme principal qui permet de lire les entrees en parametre et de faire
/// appel a la methode coventionnelle pour faire la multiplication des matrices.
///
////////////////////////////////////////////////////////////////////////////////
int main(int argv, char* argc[])
{
  if(argv < 3)
  {
    cerr << "2 parametre requis: fichier1 fichier2" << endl;
    return -1;
  }

  matrice a(argc[1]);
  matrice b(argc[2]);
  int affichage = atoi(argc[3]);

  // Verification que les 2 matrices sont charges
  if(a.size == 0 || b.size == 0)
  {
    cerr << "Probleme avec une des matrices." << endl;
    return -2;
  }

  int taille = a.size;

  // Calcul de la matrice resultante de la multiplication des 2 matrices chargees
  matrice c = strassen(a, b, taille);

  // Verificafion du boolean pour l'affichage ou non de la matrcie resultante
  if(affichage == 0)
	return 0;
  else 
  {
	c.imprimer(cout);
	return 0;
  }
}