Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <ctime>
- using namespace std;
- void strassen(int **a, int **b, int **c, int tam);
- void sum(int **a, int **b, int **result, int tam);
- void subtract(int **a, int **b, int **result, int tam);
- int **allocate_matrix(int size);
- void dealloc(int **matrix, int size);
- int main()
- {
- for(int i = 0 ; i < 3; i++)
- {
- clock_t start = clock();
- int m = 1024;
- int **A = new int*[m];
- int **B = new int*[m];
- int **product = new int*[m];
- A = allocate_matrix(m);
- B = allocate_matrix(m);
- product = allocate_matrix(m);
- for(int row = 0; row < m; row++) {
- for(int inner = 0; inner < m; inner++){
- A[row][inner] = 5;
- //cout << A[row][inner] << " ";
- }
- //cout << "\n";
- }
- for(int row = 0; row < m; row++) {
- for(int inner = 0; inner < m; inner++){
- B[row][inner] = 3;
- //cout << B[row][inner] << " ";
- }
- //cout << "\n";
- }
- /*for(int row = 0; row < m; row++) {
- for(int inner = 0; inner < m; inner++){
- product[row][inner] = 0;
- cout << product[row][inner] << " ";
- }
- cout << "\n";
- }*/
- strassen (A,B,product,m);
- //for(int row = 0; row < m; row++) {
- // for(int inner = 0; inner < m; inner++){
- // cout << product[row][inner] << " ";
- // }
- // cout << "\n";
- //}
- //deallocation
- dealloc(A, m);
- dealloc(B, m);
- dealloc(product, m);
- clock_t end = clock();
- double cpu_time = static_cast<double>(end - start)/CLOCKS_PER_SEC;
- cout << cpu_time << endl;
- }
- cout << "done" << endl;
- return 0;
- }
- void strassen(int **a, int **b, int **c, int tam) {
- // trivial case: when the matrix is 1 X 1:
- if (tam == 1) {
- c[0][0] = a[0][0] * b[0][0];
- return;
- }
- // other cases are treated here:
- int newTam = tam/2;
- int **a11, **a12, **a21, **a22;
- int **b11, **b12, **b21, **b22;
- int **c11, **c12, **c21, **c22;
- int **p1, **p2, **p3, **p4, **p5, **p6, **p7;
- // memory allocation:
- a11 = allocate_matrix(newTam);
- a12 = allocate_matrix(newTam);
- a21 = allocate_matrix(newTam);
- a22 = allocate_matrix(newTam);
- b11 = allocate_matrix(newTam);
- b12 = allocate_matrix(newTam);
- b21 = allocate_matrix(newTam);
- b22 = allocate_matrix(newTam);
- c11 = allocate_matrix(newTam);
- c12 = allocate_matrix(newTam);
- c21 = allocate_matrix(newTam);
- c22 = allocate_matrix(newTam);
- p1 = allocate_matrix(newTam);
- p2 = allocate_matrix(newTam);
- p3 = allocate_matrix(newTam);
- p4 = allocate_matrix(newTam);
- p5 = allocate_matrix(newTam);
- p6 = allocate_matrix(newTam);
- p7 = allocate_matrix(newTam);
- int **aResult = allocate_matrix(newTam);
- int **bResult = allocate_matrix(newTam);
- int i, j;
- //dividing the matrices in 4 sub-matrices:
- for (i = 0; i < newTam; i++) {
- for (j = 0; j < newTam; j++) {
- a11[i][j] = a[i][j];
- a12[i][j] = a[i][j + newTam];
- a21[i][j] = a[i + newTam][j];
- a22[i][j] = a[i + newTam][j + newTam];
- b11[i][j] = b[i][j];
- b12[i][j] = b[i][j + newTam];
- b21[i][j] = b[i + newTam][j];
- b22[i][j] = b[i + newTam][j + newTam];
- }
- }
- // Calculating p1 to p7:
- sum(a11, a22, aResult, newTam); // a11 + a22
- sum(b11, b22, bResult, newTam); // b11 + b22
- strassen(aResult, bResult, p1, newTam); // p1 = (a11+a22) * (b11+b22)
- sum(a21, a22, aResult, newTam); // a21 + a22
- strassen(aResult, b11, p2, newTam); // p2 = (a21+a22) * (b11)
- subtract(b12, b22, bResult, newTam); // b12 - b22
- strassen(a11, bResult, p3, newTam); // p3 = (a11) * (b12 - b22)
- subtract(b21, b11, bResult, newTam); // b21 - b11
- strassen(a22, bResult, p4, newTam); // p4 = (a22) * (b21 - b11)
- sum(a11, a12, aResult, newTam); // a11 + a12
- strassen(aResult, b22, p5, newTam); // p5 = (a11+a12) * (b22)
- subtract(a21, a11, aResult, newTam); // a21 - a11
- sum(b11, b12, bResult, newTam); // b11 + b12
- strassen(aResult, bResult, p6, newTam); // p6 = (a21-a11) * (b11+b12)
- subtract(a12, a22, aResult, newTam); // a12 - a22
- sum(b21, b22, bResult, newTam); // b21 + b22
- strassen(aResult, bResult, p7, newTam); // p7 = (a12-a22) * (b21+b22)
- // calculating c21, c21, c11 e c22:
- sum(p3, p5, c12, newTam); // c12 = p3 + p5
- sum(p2, p4, c21, newTam); // c21 = p2 + p4
- sum(p1, p4, aResult, newTam); // p1 + p4
- sum(aResult, p7, bResult, newTam); // p1 + p4 + p7
- subtract(bResult, p5, c11, newTam); // c11 = p1 + p4 - p5 + p7
- sum(p1, p3, aResult, newTam); // p1 + p3
- sum(aResult, p6, bResult, newTam); // p1 + p3 + p6
- subtract(bResult, p2, c22, newTam); // c22 = p1 + p3 - p2 + p6
- // Grouping the results obtained in a single matrix:
- for (i = 0; i < newTam ; i++) {
- for (j = 0 ; j < newTam ; j++) {
- c[i][j] = c11[i][j];
- c[i][j + newTam] = c12[i][j];
- c[i + newTam][j] = c21[i][j];
- c[i + newTam][j + newTam] = c22[i][j];
- }
- }
- // deallocating memory (free):
- dealloc(a11, newTam);
- dealloc(a12, newTam);
- dealloc(a21, newTam);
- dealloc(a22, newTam);
- dealloc(b11, newTam);
- dealloc(b12, newTam);
- dealloc(b21, newTam);
- dealloc(b22, newTam);
- dealloc(c11, newTam);
- dealloc(c12, newTam);
- dealloc(c21, newTam);
- dealloc(c22, newTam);
- dealloc(p1, newTam);
- dealloc(p2, newTam);
- dealloc(p3, newTam);
- dealloc(p4, newTam);
- dealloc(p5, newTam);
- dealloc(p6, newTam);
- dealloc(p7, newTam);
- dealloc(aResult, newTam);
- dealloc(bResult, newTam);
- } // end of Strassen function
- void sum(int **a, int **b, int **result, int tam) {
- int i, j;
- for (i = 0; i < tam; i++) {
- for (j = 0; j < tam; j++) {
- result[i][j] = a[i][j] + b[i][j];
- }
- }
- }
- void subtract(int **a, int **b, int **result, int tam) {
- int i, j;
- for (i = 0; i < tam; i++) {
- for (j = 0; j < tam; j++) {
- result[i][j] = a[i][j] - b[i][j];
- }
- }
- }
- int **allocate_matrix(int size) {
- int **temp = new int*[size];
- for ( int i = 0 ; i < size ; i++)
- {
- temp[i] = new int[size];
- }
- return (temp);
- }
- void dealloc (int **matrix,int size) {
- if (matrix == NULL) {
- return;
- }
- for ( int i = 0 ; i < size ; i++)
- {
- delete[] matrix[i];
- }
- delete[] matrix;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement