Optimizarea codului de inmultire a 2 matrici

Un program simplu arata cam asa:

int main() {

// a, b, c fiind matricile : input (a,b) si output (c)

int k;

for (i=0; i<=n-1; i++)

for(j=0; j<=n-1; j++) {

for(k=0; k<=n-1; k++)

c[i][j] += a[i][k]*b[k][j];

}

return 0;

}

O prima optimizare este sa pastram suma partiala intr-un registru, pentru a evita timpul de si numarul de accese la c[i][j]:

int k;

for (i=0; i<=n-1; i++)

for(j=0; j<=n-1; j++) {

register double sum = 0.0;

for(k=0; k<=n-1; k++)

sum += a[i][k]*b[k][j];

c[i][j] = sum;

}

O alta optimizare ar fi modul de accesare a lui a[i][k], b[k][j] si c[i][j] prin intermediul unor pointeri si incrementarea acestora in functie de modul de deplasare in matrice:

int k;

double *pa, *pb;

for (i=0; i<=n-1; i++) {

pa = a[0]+i*n;

for(j=0; j<=n-1; j++) {

register double sum = 0.0;

pb = b[0];

for(k=0; k<=n-1; k++) {

pa++;

pb++;

sum += (*pa) * (*pb);

}

c[i][j] = sum;

}

}

In fine, s-a facut o mica comparatie pe criteriul timp intre diverse accesari: i,k,j (varianta buna), varianta medie (primul exemplu - i,j,k) si j,k,i (varianta proasta)

Nota... toate exemplele se testeaza pe matrici de dimensiuni mai mari de 1000, pentru a se vedea mai bine efectele.