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