پیاده سازی ضرب ماتریس استراسن با کد های++C
پیاده سازی ضرب ماتریس استراسن با کد های++C
matrix strassen
فقط برای p30world
البته توی جامعه برنامه نویسان هم میزارم
داخل برنامه به اندازه کافی توضیحات هست اما اگه مشکلی داشتید من کاملا در خدمتم
در ضمن این پرژه میان ترم بود که به کمک همین سایت و یه سایت دیگه انجام شد
من شخصا قبل از نوشتن این برنامه خیلی سرچ کردم ولی هچ کدوم به این کاملی نبودند...
البته ای کاش اینجا اجازه اتچ کردن فایل داشتم تا خود برنامه رو براتون آپلود میکردم.
البته از انگیزه اصلی من مخالفت با فروش پروژه ها در وب که حتما تبلیغاتش رو دیدید.
بعضی چیز باید به طور رایگان در وب قابل دست رسی باشه...(خواهشا نقد نکنید این نظر شخصیه بزارید این تاپیک فقط برای این برنامه باشه)
کد:
//_________________--------------^^*^^--------------_____________________//
// in the name of god
//--------------------** program name strassen **----------------------//
//--------------------------- Header Files ----------------------------//
#include <conio.h>
#include <stdio.h>
#include <stdLIB.h>
#include <iostream.h>
#include <math.h>
//------------------------** Function Prototypes **----------------------//
void entermatrix(int**,int,int,int);
void addtwomatrix(int**,int**,int**,int);
void subtwomatrix(int**,int**,int**,int);
void simplemultiple(int**,int**,int**);
void printmatrix(int**,int,int);
void strassen (int**,int**,int**,int);
///-----------------------** main Function **--------------------------//
int main( )
{
int arow,acol,brow,bcol,n;
//-------------------------------------------------------- start geting matrixs
cout<<endl<<"\t\t\t -- ---**^ Hello ^**--- -- "<<endl;
cout<<endl<<endl;
cout<<" enter number colunms & rows of matrix A with own spase then enter :\t " ;
cin>>arow>>acol;
cout<<" enter number colunms & rows of matrix B with own spase then enter :\t " ;
cin>>brow>>bcol;
//-------------------------------------------------Errur
if (acol!=brow){
cout <<endl<<" Error..... colum of A matrix is not match to row of B matrix";
cout <<endl<<" OH no I am sorry you can try again now pres any key to EXIT" ;
getche();
exit(0);
}
//-------------------------------------------------max dimention
if ((arow >acol )&&(arow>bcol)) n=arow;
else
if ((acol > arow )&&(acol> bcol)) n=acol;
else n= bcol;
//------------------------------------------------cheng matrix to N*N
int counter = 1;
int m = n;
while(n/2>=2){
n = n/2;
counter++;
}
if(pow(2,counter)<m)n = pow(2,counter+1);
else
n = pow(2,counter);
///----------------------------------------** dynamic array **--------//
//-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ A
int** a_matrix = new int* [n];
for (int i = 0; i < n; i++)
a_matrix[i] = new int [n];
//-- start geting matrixs
entermatrix(a_matrix,arow,acol,n);
//-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ B
int** b_matrix = new int* [n];
for (int i = 0; i <n; i++)
b_matrix[i] = new int [n];
entermatrix(b_matrix,brow,bcol,n);
//-- for cheng to square
//-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ C
int** c_matrix = new int* [n];
for (int i = 0; i < n; i++)
c_matrix[i] = new int [n];
//------------------------------------------- multiple matrixes
strassen(a_matrix,b_matrix,c_matrix,n);
//------------------------------------------------------show target
cout<<endl<<" Matrix A =\t";
printmatrix(a_matrix,arow,acol);
cout<<endl<<" (\t*\t)"<<endl<<endl<<" Matrix b =\t";
printmatrix(b_matrix,brow,bcol);
cout<<endl<<" multiple matrix with strassen algoritm"<<endl<<endl<<endl ;
cout<<" A * B = Matrix C";
printmatrix(c_matrix,arow,bcol);
//---------------------------------------free memori
for (int i = 0; i < arow; i++)
delete a_matrix [ i ] ;
delete a_matrix ;
for (int i = 0; i < arow; i++)
delete b_matrix [ i ] ;
delete b_matrix ;
for (int i = 0; i < arow; i++)
delete c_matrix [ i ] ;
delete c_matrix ;
getch();
return 0;
}
///------------------ Function Definitions -----------------------
///------------------------------------------** enter matrix **----
void entermatrix(int **matrix,int row,int col,int n)
{
//--zero all matrix
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
matrix[i][j]=0;
//--get matrix
cout<<endl<<" Enter the values of Matrix with index (row,col) :\n "<<endl;
cout<<"\t\t\t";
for (int i=0;i<col;i++)
cout<<"-----";
cout<<endl<<"\t\t\t"<<" matrix "<<endl;
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
cout<<"\t\t\t"<<"("<< (i+1)<<","<< (j+1)<<")"<<"\t" ;
cin>>matrix[i][j];
}cout<<endl;
}
cout<<endl;
}
///---------------------------------------------** add matrixs **---//
void addtwomatrix(int **a,int **b,int **c,int n)
{
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
c[i][j] = a[i][j]+b[i][j];
}
///----------------------------------------** subtract matrixes **---//
void subtwomatrix(int **a,int **b,int **c,int n)
{
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
c[i][j] = a[i][j]-b[i][j];
}
//---------------------------------** simple multiple matrixes **----//
void simplemultiple(int **a,int **b,int **c)
{
for(int i=0;i < 2;i++)
for(int j=0;j < 2;j++)
{
c[i][j] = 0;
for(int k=0;k < 2;k++)
c[i][j] += a[i][k] * b[k][j];
}
}
///----------------------------------------------** print matrix **---\\
void printmatrix(int **c,int arow,int bcol)
{
for (int i=0;i<bcol;i++)
cout<<"\t---" ;
cout<<endl<<" \t\t\t";
for (int i=0;i<arow;i++)
{ for (int j=0;j<bcol;j++)
cout<<c[i][j]<<"\t";
cout<<endl<<" \t\t\t";}
cout<<endl<<"\t\t\t\t\t\t tank you for use strassen";
cout<<endl<<"\t\t\t\t\t\t now pres any key to EXIT" ;
}
///--------------------------------------------** strassen matrixes **---
void strassen (int **a,int **b,int **c,int n )
{
///-------------------------------- dynamic array A
int** A11 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
A11[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** A12 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
A12[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** A21 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
A21[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** A22 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
A22[i] = new int [n/2];
///-------------------------------- dynamic array B
int** B11 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
B11[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** B12 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
B12[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** B21 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
B21[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** B22 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
B22[i] = new int [n/2];
///--------------------------------- dynamic array M1,M2,M3,M4,M5,M6,M7
int** M1 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
M1[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** M2 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
M2[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** M3 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
M3[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** M4 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
M4[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** M5 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
M5[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** M6 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
M6[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** M7 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
M7[i] = new int [n/2];
///--------------------------------- dynamic array temp
int** t1 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
t1[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** t2 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
t2[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** t3 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
t3[i] = new int [n/2];
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int** t4 = new int* [n/2];
for (int i = 0; i < (n/2); i++)
t4[i] = new int [n/2];
//--------------------------- check for least minimal matrix
if(n<=2)
simplemultiple(a,b,c);
else
{
//---------------------------------- divide in to four matrix
for(int i=0;i < n / 2;i++)
for(int j=0;j < n / 2;j++) {
//------------------------------------ a to A11,A12,A21,A22
A11[i][j] = a[i ][j];
A12[i][j] = a[i ][j+n/2];
A21[i][j] = a[i+n/2][j];
A22[i][j] = a[i+n/2][j+n/2];
//------------------------------------ b to B11,B12,B21,B22
B11[i][j] = b[i ][j];
B12[i][j] = b[i ][j+n/2];
B21[i][j] = b[i+n/2][j];
B22[i][j] = b[i+n/2][j+n/2];}
//------------------------------------- calaulate M1,M2,M3,M4,M5,M6,M7
addtwomatrix(A11,A22,t1,n/2);
addtwomatrix(B11,B22,t2,n/2);
strassen(t1,t2,M1,n/2);
addtwomatrix(A21,A22,t1,n/2);
strassen(t1,B11,M2,n/2);
subtwomatrix(B12,B22,t1,n/2);
strassen(A11,t1,M3,n/2);
subtwomatrix(B21,B11,t1,n/2);
strassen(A22,t1,M4,n/2);
addtwomatrix(A11,A12,t1,n/2);
strassen(t1,B22,M5,n/2);
subtwomatrix(A21,A11,t1,n/2);
addtwomatrix(B11,B12,t2,n/2);
strassen(t1,t2,M6,n/2);
subtwomatrix(A12,A22,t1,n/2);
addtwomatrix(B21,B22,t2,n/2);
strassen(t1,t2,M7,n/2);
//-------------------------------------** calaulate C **-----------//
//-t1
addtwomatrix(M1,M4,t1,n/2);
subtwomatrix(t1,M5,t1,n/2);
addtwomatrix(t1,M7,t1,n/2);
//t2
addtwomatrix(M3,M5,t2,n/2);
//t3
addtwomatrix(M2,M4,t3,n/2);
//t4
addtwomatrix(M1,M3,t4,n/2);
subtwomatrix(t4,M2,t4,n/2);
addtwomatrix(t4,M6,t4,n/2);
//C
for(int i=0;i < n / 2;i++)
for(int j=0;j < n / 2;j++)
{
c[i ][j] = t1[i][j];
c[i ][j+n/2] = t2[i][j];
c[i+n/2][j] = t3[i][j];
c[i+n/2][j+n/2] = t4[i][j];
}
}
}
