Strassen's Matrix Multiplication

#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;
}