ضرب استراسن

[mahshid145]

سلام دوستان عزیز
نیاز به الگوریتم استراسن دارم

[fatyma]

/************************************************** ************************
************************************************** ************************
A C++ Program to computes the product of two matrices of size 4x4 using
Strassen's Algorithm (Improved Divide and Conquer Strategy).
************************************************** ************************
************************************************** ***********************/
/************************************************** ***********************
By :
Muhammad Tahir Shahzad [ MTS ]
B.C.S Honours [ 2000-04 ]
Government College University Lahore
Pakistan
E-mail : mtshome@wol.net.pk
Web-Site : www.mts-home.cjb.net (http://www.mts-home.cjb.net/) [ www.wol.net.pk/mtshome (http://www.wol.net.pk/mtshome) ]
www.mtshome.cjb.net (http://www.mtshome.cjb.net/) [ www.geocities.com/mtahirshahzad (http://www.geocities.com/mtahirshahzad) ]
************************************************** ***********************/

/************************************************** ***********************/
/************************************************** ***********************/
//--------------------------- Header Files ----------------------------//
/************************************************** ***********************/
/************************************************** ***********************/
# include <iostream.h>
# include <conio.h>
/************************************************** ***********************/
/************************************************** ***********************/
//------------------------ Global Variabbles --------------------------//
/************************************************** ***********************/
/************************************************** ***********************/
int matrix_A[4][4]={0};
int matrix_B[4][4]={0};
int matrix_C[4][4]={0};
/************************************************** ***********************/
/************************************************** ***********************/
//------------------------ Function Prototypes ------------------------//
/************************************************** ***********************/
/************************************************** ***********************/
void get_matrix_A( );
void get_matrix_B( );
void multiply_matrices( );
void show_matrix_C( );
void add_2x2_matrices(const int [2][2],const int [2][2],int [2][2]);
void subtract_2x2_matrices(const int [2][2],const int [2][2],int [2][2]);
void multiply_2x2_matrices(const int [2][2],const int [2][2],int [2][2]);
/************************************************** ***********************/
/************************************************** ***********************/
//----------------------------- main( ) -------------------------------//
/************************************************** ***********************/
/************************************************** ***********************/
int main( )
{
clrscr( );
textmode(C4350);
get_matrix_A( );
get_matrix_B( );
multiply_matrices( );
show_matrix_C( );
cout<<"\n\n\n\n\n Press any key to exit...";
getch( );
return 0;
}
/************************************************** ***********************/
/************************************************** ***********************/
//------------------------ Function Definitions -----------------------//
/************************************************** ***********************/
/************************************************** ***********************/
/************************************************** *********************/
//-------------------------- get_matrix_A( ) ------------------------//
/************************************************** *********************/
void get_matrix_A( )
{
gotoxy(1,2);
cout<<" Enter the values of Matrix-A row by row :\n "<<endl;
cout<<"\t\t\t &Uacute; &iquest;"<<endl;
cout<<"\t\t\t ³ ³"<<endl;
cout<<"\t\t\t ³ ³"<<endl;
cout<<"\t\t\t ³ ³"<<endl;
cout<<"\t\t\t ³ ³"<<endl;
cout<<"\t\t\t &Agrave; &Ugrave;"<<endl;
gotoxy(18,6);
cout<<" A = "<<endl;
int x=28;
int y=5;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
gotoxy(x,y);
cin>>matrix_A[i][j];
x+=5;
}
x=28;
y++;
}
}
/************************************************** *********************/
//------------------------- get_matrix_B( ) -------------------------//
/************************************************** *********************/
void get_matrix_B( )
{
gotoxy(1,15);
cout<<" Enter the values of Matrix-B row by row :\n "<<endl;
cout<<"\t\t\t &Uacute; &iquest;"<<endl;
cout<<"\t\t\t ³ ³"<<endl;
cout<<"\t\t\t ³ ³"<<endl;
cout<<"\t\t\t ³ ³"<<endl;
cout<<"\t\t\t ³ ³"<<endl;
cout<<"\t\t\t &Agrave; &Ugrave;"<<endl;
gotoxy(18,19);
cout<<" B = "<<endl;
int x=28;
int y=18;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
gotoxy(x,y);
cin>>matrix_B[i][j];
x+=5;
}
x=28;
y++;
}
}
/************************************************** ***********************/
//------------------------ add_2x2_matrices( ) ------------------------//
/************************************************** ***********************/
void add_2x2_matrices(const int a[2][2],const int b[2][2],int c[2][2])
{
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
c[i][j]=(a[i][j]+b[i][j]);
}
}
/************************************************** ***********************/
//----------------------- subtract_2x2_matrices( ) --------------------//
/************************************************** ***********************/
void subtract_2x2_matrices(const int a[2][2],const int b[2][2],int c[2][2])
{
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
c[i][j]=(a[i][j]-b[i][j]);
}
}
/************************************************** ***********************/
//---------------------- multiply_2x2_matrices( ) ---------------------//
/************************************************** ***********************/
void multiply_2x2_matrices(const int a[2][2],const int b[2][2],int c[2][2])
{
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[j][k]*b[k][j]);
}
}
}
/************************************************** ***********************/
//----------------------- multiply_matrices( ) ------------------------//
/************************************************** ***********************/
void multiply_matrices( )
{
int A11[2][2]={0};
int A12[2][2]={0};
int A21[2][2]={0};
int A22[2][2]={0};
int B11[2][2]={0};
int B12[2][2]={0};
int B21[2][2]={0};
int B22[2][2]={0};
int C11[2][2]={0};
int C12[2][2]={0};
int C21[2][2]={0};
int C22[2][2]={0};
int i;
int j;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
A11[i][j]=matrix_A[i][j];
B11[i][j]=matrix_B[i][j];
}
}
for(i=0;i<2;i++)
{
for(j=2;j<4;j++)
{
A12[i][(j-2)]=matrix_A[i][j];
B12[i][(j-2)]=matrix_B[i][j];
}
}
for(i=2;i<4;i++)
{
for(j=0;j<2;j++)
{
A21[(i-2)][j]=matrix_A[i][j];
B21[(i-2)][j]=matrix_B[i][j];
}
}
for(i=2;i<4;i++)
{
for(j=2;j<4;j++)
{
A22[(i-2)][(j-2)]=matrix_A[i][j];
B22[(i-2)][(j-2)]=matrix_B[i][j];
}
}
int M1[2][2]={0};
int M2[2][2]={0};
int M3[2][2]={0};
int M4[2][2]={0};
int M5[2][2]={0};
int M6[2][2]={0};
int M7[2][2]={0};
int Temp1[2][2]={0};
int Temp2[2][2]={0};
subtract_2x2_matrices(A12,A22,Temp1);
add_2x2_matrices(B21,B22,Temp2);
multiply_2x2_matrices(Temp1,Temp2,M1);
add_2x2_matrices(A11,A22,Temp1);
add_2x2_matrices(B11,B22,Temp2);
multiply_2x2_matrices(Temp1,Temp2,M2);
subtract_2x2_matrices(A11,A21,Temp1);
add_2x2_matrices(B11,B12,Temp2);
multiply_2x2_matrices(Temp1,Temp2,M3);
add_2x2_matrices(A11,A12,Temp1);
multiply_2x2_matrices(Temp1,B22,M4);
subtract_2x2_matrices(B12,B22,Temp1);
multiply_2x2_matrices(Temp1,A11,M5);
subtract_2x2_matrices(B21,B11,Temp1);
multiply_2x2_matrices(Temp1,A22,M6);
add_2x2_matrices(A21,A22,Temp1);
multiply_2x2_matrices(Temp1,B11,M7);
add_2x2_matrices(M1,M6,Temp1);
subtract_2x2_matrices(M2,M4,Temp2);
add_2x2_matrices(Temp1,Temp2,C11);
add_2x2_matrices(M4,M5,C12);
add_2x2_matrices(M6,M7,C21);
subtract_2x2_matrices(M2,M3,Temp1);
subtract_2x2_matrices(M5,M7,Temp2);
add_2x2_matrices(Temp1,Temp2,C22);
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
matrix_C[i][j]=C11[i][j];
}
for(i=0;i<2;i++)
{
for(j=2;j<4;j++)
matrix_C[i][j]=C12[i][(j-2)];
}
for(i=2;i<4;i++)
{
for(j=0;j<2;j++)
matrix_C[i][j]=C21[(i-2)][j];
}
for(i=2;i<4;i++)
{
for(j=2;j<4;j++)
matrix_C[i][j]=C22[(i-2)][(j-2)];
}
}
/************************************************** *********************/
//------------------------ show_matrix_C( ) -------------------------//
/************************************************** *********************/
void show_matrix_C( )
{
gotoxy(1,28);
cout<<" Values of Matrix-C row by row :\n "<<endl;
cout<<"\t\t\t &Uacute; &iquest;"<<endl;
cout<<"\t\t\t ³ ³"<<endl;
cout<<"\t\t\t ³ ³"<<endl;
cout<<"\t\t\t ³ ³"<<endl;
cout<<"\t\t\t ³ ³"<<endl;
cout<<"\t\t\t &Agrave; &Ugrave;"<<endl;
gotoxy(18,32);
cout<<" C = "<<endl;
int x=28;
int y=31;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
gotoxy(x,y);
cout<<matrix_C[i][j];
x+=5;
}
x=28;
y++;
}
}
/************************************************** ***********************/
/************************************************** ***********************/
//----------------------------- End of File ---------------------------//
/************************************************** ***********************/
/************************************************** ***********************/

[amarfard]

يك سوالي استادمان داده كه مي خواستم اگه كسي جوابشو مي دونه به من هم بگه!
سوال اينه كه الگوريتمي بنويسيد كه زمان پيچيدگي كمتري نسبت به استراسن داشته باشد؟
ممنون مي شم اگه يكي كمكم كنه؟

[lizbazar]

winograd ، سریع ترین الگوریتم ضرب دو ماتریس و از مرتبه ( O(n^2.376

به این پست مراجعه کنید .........

http://barnamenevis.org/forum/showthread.php?t=154396

[adele sabz]

من الگوریتم 4*4 استراسن را به همراه الگوریتم کاپر اسمیت و وینگو گراد رو می خواستم. می شه رو میلم بفرستید.ممنون