#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int mat_add=0;
int mat_mul=0;
int str_add=0;
int str_mul=0;
double str_time=0.0;
double mat_time=0.0;
void matrix_subtract(int, int**, int**, int***);
void matrix_sum(int, int**,int**,int***);
void matmul(int n, int **A, int **B, int ***C)
{
int i, j, k;
int start=clock();
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
(*C)[i][j] = 0;
for (k = 0; k < n; k++){
(*C)[i][j] = (*C)[i][j] + A[i][k] * B[k][j];
mat_add++;
mat_mul++;
}
}
}
int end=clock();
mat_time=(double)(end-start)/CLOCKS_PER_SEC;
}
void strassen_mul(int n,int** A,int** B,int*** C){
int start=clock();
int m1=(A[0][0]+A[1][1])*(B[0][0]+B[1][1]);
int m2=(A[1][0]+A[1][1])*B[0][0];
int m3=A[0][0]*(B[0][1]-B[1][1]);
int m4=A[1][1]*(B[1][0]-B[0][0]);
int m5=(A[0][0]+A[0][1])*B[1][1];
int m6=(A[1][0]-A[0][0])*(B[0][0]+B[0][1]);
int m7=(A[0][1]-A[1][1])*(B[1][0]+B[1][1]);
(*C)[0][0]=m1+m4-m5+m7;
(*C)[0][1]=m3+m5;
(*C)[1][0]=m2+m4;
(*C)[1][1]=m1+m3-m2+m6;
int end=clock();
str_time+=(end-start);
str_add+=18;
str_mul+=7;
}
void strassen(int n, int **A, int **B,int ***C)
{
if (n < 3)
strassen_mul(n,A, B, C);
else
{
int i, j, r, c;
int **A_11 = (int**)malloc(sizeof(int*)*n / 2);
int **A_12 = (int**)malloc(sizeof(int*)*n / 2);
int **A_21 = (int**)malloc(sizeof(int*)*n / 2);
int **A_22 = (int**)malloc(sizeof(int*)*n / 2);
int **B_11 = (int**)malloc(sizeof(int*)*n / 2);
int **B_12 = (int**)malloc(sizeof(int*)*n / 2);
int **B_21 = (int**)malloc(sizeof(int*)*n / 2);
int **B_22 = (int**)malloc(sizeof(int*)*n / 2);
int **C_11 = (int**)malloc(sizeof(int*)*n / 2);
int **C_12 = (int**)malloc(sizeof(int*)*n / 2);
int **C_21 = (int**)malloc(sizeof(int*)*n / 2);
int **C_22 = (int**)malloc(sizeof(int*)*n / 2);
int **temp_A = (int**)malloc(sizeof(int*)*n / 2);
int **temp_B = (int**)malloc(sizeof(int*)*n / 2);
int **M1 = (int**)malloc(sizeof(int*)*n / 2);
int **M2 = (int**)malloc(sizeof(int*)*n / 2);
int **M3 = (int**)malloc(sizeof(int*)*n / 2);
int **M4 = (int**)malloc(sizeof(int*)*n / 2);
int **M5 = (int**)malloc(sizeof(int*)*n / 2);
int **M6 = (int**)malloc(sizeof(int*)*n / 2);
int **M7 = (int**)malloc(sizeof(int*)*n / 2);
for (i = 0; i < n / 2; i++)
{
A_11[i] = (int *)malloc(sizeof(int)*n / 2);
A_12[i] = (int *)malloc(sizeof(int)*n / 2);
A_21[i] = (int *)malloc(sizeof(int)*n / 2);
A_22[i] = (int *)malloc(sizeof(int)*n / 2);
B_11[i] = (int *)malloc(sizeof(int)*n / 2);
B_12[i] = (int *)malloc(sizeof(int)*n / 2);
B_21[i] = (int *)malloc(sizeof(int)*n / 2);
B_22[i] = (int *)malloc(sizeof(int)*n / 2);
C_11[i] = (int *)malloc(sizeof(int)*n / 2);
C_12[i] = (int *)malloc(sizeof(int)*n / 2);
C_21[i] = (int *)malloc(sizeof(int)*n / 2);
C_22[i] = (int *)malloc(sizeof(int)*n / 2);
temp_A[i] = (int *)malloc(sizeof(int)*n / 2);
temp_B[i] = (int *)malloc(sizeof(int)*n / 2);
M1[i] = (int *)malloc(sizeof(int)*n / 2);
M2[i] = (int *)malloc(sizeof(int)*n / 2);
M3[i] = (int *)malloc(sizeof(int)*n / 2);
M4[i] = (int *)malloc(sizeof(int)*n / 2);
M5[i] = (int *)malloc(sizeof(int)*n / 2);
M6[i] = (int *)malloc(sizeof(int)*n / 2);
M7[i] = (int *)malloc(sizeof(int)*n / 2);
}
r = 0, c = 0;
for (i = 0; i < n; i++)
{
c = 0;
for (j = 0; j < n; j++)
{
if (i < n / 2 && j< n/2)
{
A_11[i][j] = A[i][j];
B_11[i][j] = B[i][j];
temp_A[i][j] = 0;
temp_B[i][j] = 0;
C_11[i][j] = 0;
C_12[i][j] = 0;
C_21[i][j] = 0;
C_22[i][j] = 0;
}
else if (i >= n / 2 && j < n / 2)
{
A_21[r][j] = A[i][j];
B_21[r][j] = B[i][j];
}
else if (i < n / 2 && j >= n / 2)
{
A_12[i][c] = A[i][j];
B_12[i][c] = B[i][j];
}
else if (i >= n/2 && j >= n/2)
{
A_22[r][c] = A[i][j];
B_22[r][c] = B[i][j];
}
if (j >= n / 2) c++;
}
if (i >= n / 2) r++;
}
r = 0, c = 0;
//M1
matrix_sum(n/2,A_11, A_22, &temp_A);
matrix_sum(n / 2, B_11, B_22, &temp_B);
strassen(n / 2, temp_A, temp_B, &M1);
//M2
matrix_sum(n / 2, A_21, A_22,&temp_A);
strassen(n / 2, temp_A, B_11, &M2);
//M3
matrix_subtract(n / 2, B_12, B_22, &temp_B);
strassen(n / 2, A_11, temp_B, &M3);
//M4
matrix_subtract(n / 2, B_21, B_11, &temp_B);
strassen(n / 2, A_22, temp_B, &M4);
//M5
matrix_sum(n / 2, A_11, A_12, &temp_A);
strassen(n / 2, temp_A, B_22, &M5);
//M6
matrix_subtract(n / 2, A_21, A_11, &temp_A);
matrix_sum(n / 2, B_11, B_12, &temp_B);
strassen(n / 2, temp_A, temp_B, &M6);
//M7
matrix_subtract(n / 2, A_12, A_22, &temp_A);
matrix_sum(n / 2, B_21, B_22, &temp_B);
strassen(n / 2, temp_A, temp_B, &M7);
//C_11
matrix_sum(n / 2, M1, M4, &temp_A);
matrix_subtract(n / 2, temp_A, M5, &temp_B);
matrix_sum(n / 2, temp_B, M7, &C_11);
//C_12
matrix_sum(n / 2, M3, M5, &C_12);
//C_21
matrix_sum(n / 2, M2, M4, &C_21);
//C_22
matrix_sum(n / 2, M1, M3, &temp_A);
matrix_subtract(n / 2, temp_A, M2, &temp_B);
matrix_sum(n / 2, temp_B, M6, &C_22);
for (i = 0; i < n; i++)
{
c = 0;
for (j = 0; j < n; j++)
{
if (i < n / 2 && j < n / 2)
{
(*C)[i][j] = C_11[i][j];
}
else if (i >= n / 2 && j < n / 2)
{
(*C)[i][j] = C_21[r][j];
}
else if (i < n / 2 && j >= n / 2)
{
(*C)[i][j] = C_12[i][c];
}
else if (i >= n / 2 && j >= n / 2)
{
(*C)[i][j] = C_22[r][c];
}
if (j >= n / 2) c++;
}
if (i >= n / 2) r++;
}
for (i = 0; i < n / 2; i++)
{
free(A_11[i]); free(A_12[i]); free(A_21[i]); free(A_22[i]);
free(B_11[i]); free(B_12[i]); free(B_21[i]); free(B_22[i]);
free(C_11[i]); free(C_12[i]); free(C_21[i]); free(C_22[i]);
free(temp_A[i]); free(temp_B[i]);
free(M1[i]); free(M2[i]); free(M3[i]); free(M4[i]); free(M5[i]); free(M6[i]); free(M7[i]);
}
free(A_11); free(A_12); free(A_21); free(A_22);
free(B_11); free(B_12); free(B_21); free(B_22);
free(C_11); free(C_12); free(C_21); free(C_22);
free(temp_A); free(temp_B);
free(M1); free(M2); free(M3); free(M4); free(M5); free(M6); free(M7);
}
}
void matrix_sum(int n, int **A, int **B, int ***C)
{
int i,j;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
(*C)[i][j] = A[i][j] + B[i][j];
}
}
}
void matrix_subtract(int n, int **A, int **B, int ***C)
{
int i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
(*C)[i][j] = A[i][j] - B[i][j];
}
}
}
int main(){
int n;
scanf("%d",&n);
int i,j;
int **matrix_A = (int **)malloc(sizeof(int*) *n);
int **matrix_B = (int **)malloc(sizeof(int*) *n);
int **matrix_C = (int **)malloc(sizeof(int*) *n);
for (i = 0; i < n; i++)
{
matrix_A[i] = (int *)malloc(sizeof(int)*n);
matrix_B[i] = (int *)malloc(sizeof(int)*n);
matrix_C[i] = (int *)malloc(sizeof(int)*n);
}
srand(time(0));
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
matrix_A[i][j] = (rand()%10) ;
matrix_B[i][j] = (rand()%10) ;
matrix_C[i][j] = 0;
}
}
matmul(n,matrix_A, matrix_B, &matrix_C);
for (i=0; i<n; i++ )
memset(matrix_C[ i ], 0, sizeof(*matrix_C));
strassen(n,matrix_A, matrix_B, &matrix_C);
for (i = 0; i < n; i++)
{
free(matrix_A[i]); free(matrix_B[i]); free(matrix_C[i]);
}
free(matrix_A);
free(matrix_B);
free(matrix_C);
printf("%f %f\n",str_add, str_mul);
printf("%f %f",(double)mat_time/CLOCKS_PER_SEC, (double)str_time/CLOCKS_PER_SEC);
}
}
