[c++] eccovi una function per fare il prodotto tra matrici di grandezza desiderata

[vermaccio]

a chi servisse ecco TRE funzioni che fanno la stessa cosa, compreso un esempio di test (usato matlab e matrici 4X4).

Lo scopo di queste funzioni è poter moltiplicare due matrici di grandezza "qualsiasi" (leggi nota in fondo) senza dover scrivere una funzione diversa se cambia la grandezza della matrice. non usando il sistema di puntatori che abbiamo implementato si dichiara nella intestazione della funione quante colonne ha la matrice e quindi non si può usare per una matrice con numero di colonne diverso. Invece con queste due function (identiche per risultati ma diverse per scrittura) basta passare le due matrici di input, il nome della matrice di output e le dimensioni di esse.


1

listato c++ di vermaccio
(per vedere tutto il suo sviluppo vedere
http://www.hwupgrade.it/forum/showpo...2&postcount=33
Ringrazio "andbin": senza la sua gentilezza, la sua pazienza e le sue infinite spiegazioni illuminanti non avrei mai potuto capire i puntatori.
Il cuore dell'algoritmo "puntatori" lo ha creato lui. Io l'ho applicato al caso del prodotto tra matrici.)

#include<stdio.h>
#include <math.h>

double A[2][2]= { {1, 2},{3,4} };
double B[2][2]= { {5,6},{7,-8} };
double C[4][3]= { {1, -2, 3},{-5, 0, 7},{-2, -1, 5},{3, 0, -1} };
double D[3][4]= { {1, 2, 3, 4},{5, 6, 7, 8},{-2, 1, -5, 12} };



double AB[2][2];
double CD[4][4];



//XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
//funzione prodotto di due matrici   XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

void prodottomatrici(double *matrA, int nrigA, int ncolA, double *matrB, int nrigB, int ncolB, double *matrC, int nrigC, int ncolC)  {

//i=righeA
//j=colonneB
//k=colonneA=righeB !!!!!!! se colonneA diverso da righeB si ha errore

int i, j, k; //variabili locali
double elemA, elemB, elemC; //variabili locali

for (i=0; i<nrigA; i++){ //scorro riga di matrice risultato
	for (j=0; j<ncolB; j++){  //scorro colonna di matrice risultato
		elemC=0; // sarebbe la matC[i][j]=0;
			for (k=0; k<ncolA; k++){  //oppure k<nrigB visto che ncolA=nrigB
				elemA = *(matrA + i * ncolA + k); //sarebbe la matA[i][k]
				elemB = *(matrB + k * ncolB + j); //sarebbe la matB[k][j]
				
				elemC = elemC+elemA*elemB; //sarebbe la matC[i][j]=matC[i][j]+matA[i][k]*matB[k][j];
				//test=A[i][k]*B[k][j];
				//printf("%g\n", test );
							}
		*(matrC + i * ncolC + j) = elemC;//ora assegno il risultato "elemC" alla matrice di uscita assegnando al puntatore 
	                                             //adatto relativo alla giusta cella della matrice quel valore "elemC"
				
            //printf("%g\n", matC[i][j] );
			}


	}

	
}








//--------------------
void main(void)
{

//notare gli [0][0] perchè sto passando i puntatori alprimo elemento della matrice
prodottomatrici (&A[0][0], 2, 2, &B[0][0], 2, 2, &AB[0][0], 2, 2); 
printf("elemento [1][1] matrice prodotto A*B: %g\n", AB[0][0] );
printf("elemento [1][2] matrice prodotto A*B: %g\n", AB[0][1] );
printf("elemento [2][1] matrice prodotto A*B: %g\n", AB[1][0] );
printf("elemento [2][2] matrice prodotto A*B: %g\n", AB[1][1] );


printf("--------------------------  \n");


//notare gli [0][0] perchè sto passando i puntatori alprimo elemento della matrice
prodottomatrici (&C[0][0], 4, 3, &D[0][0], 3, 4, &CD[0][0], 4, 4);
printf("elemento [1][1] matrice prodotto C*D: %g\n", CD[0][0] );
printf("elemento [1][2] matrice prodotto C*D: %g\n", CD[0][1] );
printf("elemento [1][3] matrice prodotto C*D: %g\n", CD[0][2] );
printf("elemento [1][4] matrice prodotto C*D: %g\n", CD[0][3] );

printf("elemento [2][1] matrice prodotto C*D: %g\n", CD[1][0] );
printf("elemento [2][2] matrice prodotto C*D: %g\n", CD[1][1] );
printf("elemento [2][3] matrice prodotto C*D: %g\n", CD[1][2] );
printf("elemento [2][4] matrice prodotto C*D: %g\n", CD[1][3] );

printf("elemento [3][1] matrice prodotto C*D: %g\n", CD[2][0] );
printf("elemento [3][2] matrice prodotto C*D: %g\n", CD[2][1] );
printf("elemento [3][3] matrice prodotto C*D: %g\n", CD[2][2] );
printf("elemento [3][4] matrice prodotto C*D: %g\n", CD[2][3] );

printf("elemento [4][1] matrice prodotto C*D: %g\n", CD[3][0] );
printf("elemento [4][2] matrice prodotto C*D: %g\n", CD[3][1] );
printf("elemento [4][3] matrice prodotto C*D: %g\n", CD[3][2] );
printf("elemento [4][4] matrice prodotto C*D: %g\n", CD[3][3] );

}



/*risultati matlab
AB =
    19   -10
    43   -14
risultato c++: OK

CD =
   -15    -7   -26    24
   -19    -3   -50    64
   -17    -5   -38    44
     5     5    14     0
 risultato c++: OK
 */

2

Questa invece è la soluzione di andbin, soluzione contenente più sottofunzioni sepratae per fare i vari passaggi.

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    double *array;
    int     rows;
    int     columns;
} MATRIX_2D, *PMATRIX_2D;


/******************************************************************************/
/* FUNZIONI GENERICHE DI GESTIONE MATRICI                                     */
/******************************************************************************/
double Matrix2D_GetValue (PMATRIX_2D pmatrix, int r, int c)
{
    return *(pmatrix->array + r * pmatrix->columns + c);
}

void Matrix2D_SetValue (PMATRIX_2D pmatrix, int r, int c, double value)
{
    *(pmatrix->array + r * pmatrix->columns + c) = value;
}

void Matrix2D_AddValue (PMATRIX_2D pmatrix, int r, int c, double value)
{
    *(pmatrix->array + r * pmatrix->columns + c) += value;
}

int Matrix2D_Product (PMATRIX_2D pmatrix_a, PMATRIX_2D pmatrix_b, PMATRIX_2D pmatrix_out)
{
    int rows, columns, r, c, i;

    if (pmatrix_a->columns != pmatrix_b->rows)
        return 0;   /* Errore, matrici non compatibili! */

    rows = pmatrix_a->rows;
    columns = pmatrix_b->columns;

    /* Allocazione matrice del prodotto */
    pmatrix_out->array = (double*) malloc (rows * columns * sizeof (double));
    pmatrix_out->rows = rows;
    pmatrix_out->columns = columns;

    for (r = 0; r < rows; r++)
    {
        for (c = 0; c < columns; c++)
        {
            Matrix2D_SetValue (pmatrix_out, r, c, 0.0);

            for (i = 0; i < pmatrix_a->columns; i++)
            {
                Matrix2D_AddValue (pmatrix_out, r, c,
                    Matrix2D_GetValue (pmatrix_a, r, i) *
                    Matrix2D_GetValue (pmatrix_b, i, c));
            }
        }
    }

    return 1;   /* Successo */
}

void Matrix2D_Free (PMATRIX_2D pmatrix)
{
    free (pmatrix->array);
}

void Matrix2D_Print (PMATRIX_2D pmatrix)
{
    int r, c;

    for (r = 0; r < pmatrix->rows; r++)
    {
        for (c = 0; c < pmatrix->columns; c++)
        {
            if (c > 0)
                printf (" ");

            printf ("%9.3f", Matrix2D_GetValue (pmatrix, r, c));
        }

        printf ("\n");
    }
}


/******************************************************************************/
/* MAIN                                                                       */
/******************************************************************************/
double a[4][3]= { {1, -2, 3}, {-5, 0, 7}, {-2, -1, 5}, {3, 0, -1} };
double b[3][4]= { {1, 2, 3, 4}, {5, 6, 7, 8}, {-2, 1, -5, 12} };


int main (void)
{
    MATRIX_2D matrix_a = { &a[0][0], 4, 3 };
    MATRIX_2D matrix_b = { &b[0][0], 3, 4 };

    MATRIX_2D matrix_prod;

    if (Matrix2D_Product (&matrix_a, &matrix_b, &matrix_prod) != 0)
    {
        printf ("Matrice A\n");
        Matrix2D_Print (&matrix_a);

        printf ("\n");
        printf ("Matrice B\n");
        Matrix2D_Print (&matrix_b);

        printf ("\n");
        printf ("Matrice Prodotto\n");
        Matrix2D_Print (&matrix_prod);

        Matrix2D_Free (&matrix_prod);
    }

    return 0;
}

3

Listato di sottovento che, però, prevede prima una linearizzazione delle matrici ovvero una matrice A[m][n] (=array bidimensionale) deve essere prima trasformata in vettore monodimensionale A[m*n]

esempio
A[4][3] --> A[12]
e ala funzione gli passi in input A[12] e non più A[4][3].

int mult(double *matrA, int rowsA, int colsA, 
         double *matrB, int rowsB, int colsB, 
         double *matrC, int rowsC, int colsC)
{
  int i, h, k; // counters
  double elemC; // Temporary variables for calculation
  // These are pointers to the corresponding current matrix' element
  double *p2a, *p2b, *p2c;

  // Check for right sizes
  if (rowsA != rowsC ||
      colsB != colsC ||
      colsA != rowsB)
  {
    // Cannot perform this operation. Wrong sizes
    return -1;
  }

  p2c = matrC;
  for (h = 0; h < rowsA; h++)
  {
    for (i = 0; i < colsB; i++)
    {
      p2a = matrA + h * colsA;
      p2b = matrB + i;
      elemC = 0.0;
      for (k = 0; k < colsA; k++)
      {
        elemC += *p2a++ * *p2b;
        p2b += colsB;
      }
      *p2c++ = elemC;
    }
  }
  return 0;
}

TEST:
con matlab (un programma matematico che esegue questi calcoli matriciali senza fatica) ho fatto i conti ed abbiamo verificato che i due programmi dessero lo stesso risultato. perfetto. funzionano.

Matrice A
    1.000    -2.000     3.000
   -5.000     0.000     7.000
   -2.000    -1.000     5.000
    3.000     0.000    -1.000

Matrice B
    1.000     2.000     3.000     4.000
    5.000     6.000     7.000     8.000
   -2.000     1.000    -5.000    12.000

Matrice Prodotto A*B calcolata dai programmi
  -15.000    -7.000   -26.000    24.000
  -19.000    -3.000   -50.000    64.000
  -17.000    -5.000   -38.000    44.000
    5.000     5.000    14.000     0.000

OK!
i programmi funzionano!
essendo molti cicli for anndati e molte sommatorie e prodotti, se funziona con una matrice 4X4 è logico supporre che funzioni swempre. comunque se si usa il prgramma per fare calcoli grafici (matrici roto-traslazionali) di solito si usano proprio matrici 4X4

nota finale:

le dimensioni delle matrici da moltiplicare NON devono essere casuali.

se si hanno due matrici
A[a][b]
B[m][n]

per moltiplicare A*B
DEVE essere b=m
e la matrice che si ottiene è
C[a][n]=A*B

B*A=D[m][b] ma deve essere n=a

logicamente B*A è DIVERSO da A*B
(in calcolo matriciale NON vale la regola della matematica che due numeri moltiplicati danno lo stesso risultato se scambiati tra loro es: 2*3=3*2). quindi quando usate la funzione occhio a che matrice inseriote per prima e quale per seconda in input!!!!

[Ziosilvio]

Non male.

Adesso però riscrivi la main in modo che abbia tipo int, come vuole lo standard del C++.

[sottovento]

Ciao
due osservazioni:

1 - Prima di eseguire il prodotto fra matrici, occorre verificare che le matrici siano conformabili. E' opportuno che aggiunga questo controllo;

2 - L'uso dei puntatori che fai all'interno del programma e' equivalente all'uso delle parentesi quadre.
Per esempio, se hai
double *vet;
Le istruzioni
double tmp = *(vet + i);
e
double tmp = vet[i];
Sono equivalenti. Sara' una questione soggettiva, ma la seconda mi sembra piu' leggibile.
Nel caso delle operazioni che vuoi fare, i puntatori possono essere usati per ridurre il numero delle operazioni da effettuare, ottimizzando i tempi di esecuzione.

High Flying
Sottovento

[vermaccio]

Originariamente inviato da Ziosilvio

Non male.

Adesso però riscrivi la main in modo che abbia tipo int, come vuole lo standard del C++.

ehm.. ovvero?
uso da poco c++ e mi servono spiegazioni....

[vermaccio]

Originariamente inviato da sottovento

Ciao
due osservazioni:

1 - Prima di eseguire il prodotto fra matrici, occorre verificare che le matrici siano conformabili. E' opportuno che aggiunga questo controllo;

2 - L'uso dei puntatori che fai all'interno del programma e' equivalente all'uso delle parentesi quadre.
Per esempio, se hai
double *vet;
Le istruzioni
double tmp = *(vet + i);
e
double tmp = vet[i];
Sono equivalenti. Sara' una questione soggettiva, ma la seconda mi sembra piu' leggibile.
Nel caso delle operazioni che vuoi fare, i puntatori possono essere usati per ridurre il numero delle operazioni da effettuare, ottimizzando i tempi di esecuzione.

High Flying
Sottovento

non conosco ancora bene i puntatori.
diciamo che per motivi di urgenza mi serviva far funzionare il programma. ora devo migliorarlo per ottimizzarlo.

comunque.

elemA = *(matrA + i * ncolA + k);

con i puntatori che diventarebbe?

elema=matrA[i*ncolA+k]?
mmmm...... mi pare strano visto che è un array bidimensionale. manche rebbe l'altra [].

comunque le matrici in ingrasso sono array bidimensionali e non pntatori.

si potrebbe trasformare tutto in puntatori.
ma ha senso?
conviene usare i puntatori o gli array in c++ se si devono fare calcoli con molti cicli for annidati come questo prodotto di matrici?

[sottovento]

Originariamente inviato da vermaccio

... omissis ...
elemA = *(matrA + i * ncolA + k);

con i puntatori che diventarebbe?

elema=matrA[i*ncolA+k]?
mmmm...... mi pare strano visto che è un array bidimensionale. manche rebbe l'altra [].

Direi che va benissimo, invece. Non hai dichiarato array bidimensionali.
Ovviamente si tratta di un problema di leggibilita', quindi soggettivo.

High Flying
Sottovento

[andbin]

Originariamente inviato da sottovento

2 - L'uso dei puntatori che fai all'interno del programma e' equivalente all'uso delle parentesi quadre.
Per esempio, se hai
double *vet;
Le istruzioni
double tmp = *(vet + i);
e
double tmp = vet[i];
Sono equivalenti.

Uff .... certo! Questo è vero, in generale, ma solo se il compilatore conosce a priori le caratteristiche dell'array. Per un array a 1 dimensione le due espressioni che hai riportato sopra sono sempre equivalenti.
Per un array a 2 dimensioni, la cosa è un po' diversa. Il compilatore deve sapere a priori quante colonne ha l'array.
double arr[3][4];

double tmp = *(arr + i*4 + j);
e
double tmp = arr[i][j];
Sono certamente equivalenti.

Il problema di vermaccio era quello di voler passare alla funzione un array bidimensionale di dimensione arbitraria (quindi la funzione non deve conoscere a priori le dimensioni).

In questo caso l'unica possibilità è quella di passare un semplice puntatore double *arr alla funzione (passando separatamente alla funzione anche le due dimensioni, ovviamente!) e fare "a mano" l'aritmetica dei puntatori per accedere alla cella dell'array.

Avendo un semplice puntatore, NON puoi fare arr[i][j], perché il compilatore non saprebbe quante colonne ha l'array!!!!

Ah ... i puntatori ...

[vermaccio]

Il problema di vermaccio era quello di voler passare alla funzione un array bidimensionale di dimensione arbitraria (quindi la funzione non deve conoscere a priori le dimensioni).

il motivo della scrittura così "strana" della funzione è proprio questo: si getta in pasto alla funzione una matrice di dimensione qualsiasi.

se avessimo scritto nell'intestazione della funzione matrA[4][4] invece di *matrA[0][0] avremmo potuto passare in input SOLO matrice 4X4 e non di dimensione voluta. quindi se avessimo voluto inserire una matrice 3X3 avremmo dovuto scrivere una seconda funzione specifica. insomma non finivamo più di scrivere infinite funzioni per infinite possibilità di moltiplicare matrici di dimensioni diverse (anche tra loro!)

[cionci]

Avete un po' programmato alla C...non alla C++

[sottovento]

Originariamente inviato da andbin

Uff .... certo! Questo è vero, in generale, ma solo se il compilatore conosce a priori le caratteristiche dell'array. Per un array a 1 dimensione le due espressioni che hai riportato sopra sono sempre equivalenti.
Per un array a 2 dimensioni, la cosa è un po' diversa. Il compilatore deve sapere a priori quante colonne ha l'array.
double arr[3][4];

double tmp = *(arr + i*4 + j);
e
double tmp = arr[i][j];
Sono certamente equivalenti.

Il problema di vermaccio era quello di voler passare alla funzione un array bidimensionale di dimensione arbitraria (quindi la funzione non deve conoscere a priori le dimensioni).

In questo caso l'unica possibilità è quella di passare un semplice puntatore double *arr alla funzione (passando separatamente alla funzione anche le due dimensioni, ovviamente!) e fare "a mano" l'aritmetica dei puntatori per accedere alla cella dell'array.

Avendo un semplice puntatore, NON puoi fare arr[i][j], perché il compilatore non saprebbe quante colonne ha l'array!!!!

Ah ... i puntatori ...

Scusate, non voglio certo far nascere un caso su un problema del genere.
Comunque, se nella dichiarazione della procedura dichiari

int procedura (double *vect)

e poi intendi usarlo come array (anche bidimensionale), invece che scrivere
elemento = *(vect + i * DIM_X + h);
puoi sempre e comunque scrivere
elemento = vect[i * DIM_X + h];

in entrambi i casi, la gestione della bidimensionalita' della matrice te la gestisci.
Tutto qui, volevo solo dire che era, appunto, un problema di leggibilita'. E' chiaro che non c'e' un motivo oggettivo per preferire una scrittura rispetto all'altra.

Ribadisco anche l'altra osservazione, per vermaccio: ti conviene controllare la conformabilita' delle matrici prima di fare l'operazione. Non e' una cosa secondaria, soprattutto quando gestisci "a mano" la bidimensionalita' delle matrici.

Per quanto riguardava l'osservazione relativa all'ottimizzazione del codice, si tratta di un'ottimizzazione piuttosto ridotta: ovviamente non cambia l'ordine di grandezza del problema (che rimane O(n^3)).

L'ottimizzazione che volevo proporre e' in questo senso: come detto prima, le due scritture sono equivalenti. Quindi vet[i * dim_x + h] == *(vet + dim_x + h). Entrambi genereranno lo stesso numero di operazioni.
Infatti, i compilatori (praticamente tutti e su tutte le piattaforme), carichera' in un registro il valore "base" del vettore, calcolera' l'indice (dato dalla tua formula) e poi moltiplica il tuo indice per la dimensione del tipo base.
Quindi se il tuo tipo double, per esempio, ha dimensione 8 byte, il codice che e' stato scritto, per accedere all'elemento che vuoi:
- carica in un registro (chiamiamolo r_base) l'indirizzo di vect;
- valuta attraverso un parser l'espressione i * dim_x + h e mette il risultato in un registro, chiamiamolo r_index;
- moltiplica il contenuto di r_index per 8;
- somma il contenuto di r_index con r_base e lo pone, diciamo in r_result;

Con r_result puoi accedere all'elemento corretto.

E' chiaro che hai dei puntatori, e li puoi usare per "scorrere" le matrici: li inizializzi all'indirizzo base dei vettori. Poi uno lo incrementi di una unita', mentre l'altro gli sommi direttamente dimx. In questo modo riduci le operazioni sopra riportate.
C'e' da notare che molti processori hanno una istruzione speciale di "leggi ed incrementa" che i compilatori non mancano di utilizzare, pertanto l'istruzione
*p++
viene risolta con una sola istruzione.

Questo e' un tipico caso in cui l'uso dei puntatori puo' portare ad un aumento delle prestazioni

High Flying
Sottovento

[andbin]

Originariamente inviato da cionci

Avete un po' programmato alla C...non alla C++

Sì, è vero ... però se vuoi lo rifaccio in C++ con classi, eccezioni, ecc...

[sottovento]

Ops, stavamo scrivendo nello stesso momento. Spero non ti scappi la risposta, il parere di un esperto del tuo calibro e' sempre importante

High Flying
Sottovento

[andbin]

Originariamente inviato da sottovento

Scusate, non voglio certo far nascere un caso su un problema del genere.

Non c'è problema, figurati! Nessuno voleva fare polemiche

Originariamente inviato da sottovento

elemento = *(vect + i * DIM_X + h);
puoi sempre e comunque scrivere
elemento = vect[i * DIM_X + h];

Esatto! In pratica usando la notazione vect[nnn] lo vedi come se fosse un array ad 1 dimensione (ma naturalmente tu sai che è a 2 dimensioni e calcoli tu la locazione giusta).

A me la prima cosa che era venuta in mente, in effetti, era la prima forma ... chissà perché penso sempre le cose più complicate!

[andbin]

Originariamente inviato da sottovento

Spero non ti scappi la risposta, il parere di un esperto del tuo calibro e' sempre importante

[sottovento]

Originariamente inviato da andbin

Non era ironico, lo penso. Sinceramente

[vermaccio]

chi vuole scriverlo con i puntatori, testarlo ed incollare qui la function compreso un main di test?

[Ziosilvio]

Originariamente inviato da vermaccio

ovvero?

Ovvero: lo standard C++ prevede che main restituisca un valore di tipo int.
Tale valore deve essere 0 in caso di terminazione con successo, 1 in caso di terminazione con insuccesso, e maggiore di 1 in caso si verifichino errori.
Questo lo trovi su qualunque manuale serio di C++.

[vermaccio]

Originariamente inviato da Ziosilvio

Ovvero: lo standard C++ prevede che main restituisca un valore di tipo int.
Tale valore deve essere 0 in caso di terminazione con successo, 1 in caso di terminazione con insuccesso, e maggiore di 1 in caso si verifichino errori.
Questo lo trovi su qualunque manuale serio di C++.

ovvero invece di
void prodottomatrici(double *matrA, int nrigA, int ncolA, double *matrB, int nrigB, int ncolB, double *matrC, int nrigC, int ncolC) {

tu dici di mettere

int errore prodottomatrici(double *matrA, int nrigA, int ncolA, double *matrB, int nrigB, int ncolB, double *matrC, int nrigC, int ncolC) {

e logicamente va immesso a fine funzione return(errore);

ma come passo al programma il valore 1 se c'è errore?
come capisce il programma se c'è errore?

[71104]

ma che c'entra la funzione prodottomatrici, è la funzione main che deve restituire int

[vermaccio]

e come si fa? io non lo so davvero.