PDA

View Full Version : برنامه یا الگوریتم ضرب استراسن



nobody777
سه شنبه 15 آذر 1384, 03:14 صبح
سلام
اگر کسی که برنامه ضرب استراسن را داره
برای من هم بفرسته ممنون میشم.

aidin300
چهارشنبه 16 آذر 1384, 18:10 عصر
اینجا upload کردم

ze2005
پنج شنبه 17 آذر 1384, 00:10 صبح
لطفن یک نفر هم به من برنامه یا الگوریتم ضرب استراسن را بده

rooza_ma
پنج شنبه 17 آذر 1384, 22:54 عصر
mishe barnameye zarbe strasen ro be zaboone pascal vasam befrestid?l

pmaziarp
شنبه 24 دی 1384, 17:17 عصر
برنامه یا الگوریتم ضرب استراسن

mohammadaref
دوشنبه 26 دی 1384, 09:23 صبح
سلام
لطفا اگرکسی برنامه استراسن را داردبرایم بفرسته

hesam_187
یک شنبه 28 اسفند 1384, 10:50 صبح
آقا توی این همه آدم به نفر پیدا نمیشه این الگوریتم و داشته باشه

mohandese_hiclass
پنج شنبه 24 فروردین 1385, 01:28 صبح
دوست عزیز سعی کنید به جای سورس کد راهنمایی بخواهید البته من این حرف را فقط به خاطره خودتون میگم

mohandese_hiclass
چهارشنبه 30 فروردین 1385, 11:55 صبح
اگه سورس کد بخواهید همیشه نسبت به نویسنده سورس یه پله عقب ترید

m_g_748
پنج شنبه 14 اردیبهشت 1385, 21:07 عصر
mail بذار بفرستم
سلام اگر الگوریتم استراسن دارین ممنون میشم برام ایمیل بزنید اگه ممکن فقط سری
قربان شما و بینهایت تشکر.

powerboy2988
یک شنبه 28 آبان 1385, 17:33 عصر
الگوریتم استراسن
http://barnamenevis.org/forum/showthread.php?p=283440#post283440

hassan ghanbari
چهارشنبه 01 آذر 1385, 22:45 عصر
#include<iostream.h>
#include<stdlib.h>
#define BREAK 2
#define a11 a->p[0]
#define a12 a->p[1]
#define a21 a->p[2]
#define a22 a->p[3]
#define b11 b->p[0]
#define b12 b->p[1]
#define b21 b->p[2]
#define b22 b->p[3]
#define c11 c->p[0]
#define c12 c->p[1]
#define c21 c->p[2]
#define c22 c->p[3]
#define d11 d->p[0]
#define d12 d->p[1]
#define d21 d->p[2]
#define d22 d->p[3]
typedef double **matrix;
typedef union _strassen_matrix
{
matrix d;
union _strassen_matrix **p;
} *strassen_matrix;
matrix new_matrix(int);
strassen_matrix new_strassen(int);
void normal_to_strassen(matrix, strassen_matrix, int);
void strassen_to_normal(strassen_matrix, matrix, int);
matrix strassen_submatrix(strassen_matrix, int, int, int);
void copy_matrix(matrix, matrix, int);
void add_matrix(matrix, matrix, matrix, int);
void sub_matrix(matrix, matrix, matrix, int);
void copy_strassen(strassen_matrix, strassen_matrix, int);
void add_strassen(strassen_matrix, strassen_matrix, strassen_matrix, int);
void sub_strassen(strassen_matrix, strassen_matrix, strassen_matrix, int);
void mul_matrix(matrix, matrix, matrix, int);
void mul_strassen(strassen_matrix, strassen_matrix, strassen_matrix, strassen_matrix, int);
void print_matrix(matrix, int);
int least_power_of_two(int);

matrix new_matrix(int n)
{
matrix a = (matrix) malloc(sizeof(double *) * n);
for (int j = 0; j < n; j++)
a[j] = (double *) malloc(sizeof(double) * n);
return(a);
}
strassen_matrix new_strassen(int n)
{
strassen_matrix a;
a = (strassen_matrix)malloc(sizeof(*a));
if (n <= BREAK)
a->d = (matrix ) new_matrix(n);
else
{
register int m = n/2;
a->p = (strassen_matrix *)malloc(4*sizeof(strassen_matrix));
a11 = new_strassen(m);
a12 = new_strassen(m);
a21 = new_strassen(m);
a22 = new_strassen(m);
}
return a;
}
matrix strassen_submatrix(strassen_matrix a,
int i,
int j,
int n
)
{
if (n <= BREAK)
return(a->d);
else
{
int cur_bit, bit_num;
strassen_matrix cur_ptr = a;
bit_num = least_power_of_two(n)-1;
cur_bit = n/2;
while (cur_bit >= BREAK)
{
cur_ptr = cur_ptr->p[(((j & cur_bit) | ((i & cur_bit)*2)) >> bit_num)];
cur_bit >>= 1;
bit_num--;
}
return (cur_ptr->d);
}
}
void normal_to_strassen(matrix a,strassen_matrix b,int n)
{
if (n <= BREAK)
copy_matrix(a,b->d,n);
else
{
int i,j,ii,jj;
matrix sub;
for (i=0; i<n; i += BREAK)
{
for (j=0; j<n; j += BREAK)
{
sub = strassen_submatrix(b,i,j,n);
for (ii=0; ii<BREAK; ii++)
for (jj=0; jj<BREAK; jj++)
sub[ii][jj] = a[i+ii][j+jj];
}
}
}
}
void strassen_to_normal(strassen_matrix a,matrix b,int n)
{
if (n <= BREAK)
copy_matrix(a->d,b, n);
else
{
matrix sub;
for (int i=0; i<n; i += BREAK)
{
for (int j=0; j<n; j += BREAK)
{
sub = strassen_submatrix(a,i,j,n);
for (int ii=0; ii<BREAK; ii++)
for (int jj=0; jj<BREAK; jj++)
b[i+ii][j+jj] = sub[ii][jj];
}
}
}
}
void copy_matrix(
matrix a,
matrix b,
int n
)
{
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
b[i][j] = a[i][j];
}

void add_matrix(
matrix a,
matrix b,
matrix c,
int n
)
{
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
c[i][j] = b[i][j] + a[i][j];
}

void sub_matrix(
matrix a,
matrix b,
matrix 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];
}
void add_strassen(
strassen_matrix a,
strassen_matrix b,
strassen_matrix c,
int n
)
{
if (n <= BREAK)
add_matrix(a->d, b->d, c->d, n);
else
{
int m=n/2;
add_strassen(a11, b11, c11, m);
add_strassen(a12, b12, c12, m);
add_strassen(a21, b21, c21, m);
add_strassen(a22, b22, c22, m);
}
}
void sub_strassen(
strassen_matrix a,
strassen_matrix b,
strassen_matrix c,
int n
)
{
if (n <= BREAK)
{
sub_matrix(a->d, b->d, c->d, n);
}
else
{
int m = n/2;
sub_strassen(a11, b11, c11, m);
sub_strassen(a12, b12, c12, m);
sub_strassen(a21, b21, c21, m);
sub_strassen(a22, b22, c22, m);
}
}
void mul_matrix(
matrix a,
matrix b,
matrix c,
int n
)
{
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
c[i][j] = 0.0;
for(int k=0; k<n; k++)
c[i][j] += a[i][k] * b[k][j];
}
}
void mul_strassen(
strassen_matrix a,
strassen_matrix b,
strassen_matrix c,
strassen_matrix d,
int n
)
{
if (n <= BREAK)
mul_matrix(a->d,b->d,c->d,n);
else
{
int m = n/2;
sub_strassen(a12, a22, d11, m);
add_strassen(b21, b22, d12, m);
mul_strassen(d11, d12, c11, d21, m);
sub_strassen(a21, a11, d11, m);
add_strassen(b11, b12, d12, m);
mul_strassen(d11, d12, c22, d21, m);
add_strassen(a11, a12, d11, m);
mul_strassen(d11, b22, c12, d12, m);
sub_strassen(c11, c12, c11, m);
sub_strassen(b21, b11, d11, m);
mul_strassen(a22, d11, c21, d12, m);
add_strassen(c21, c11, c11, m);
sub_strassen(b12, b22, d11, m);
mul_strassen(a11, d11, d12, d21, m);
add_strassen(d12, c12, c12, m);
add_strassen(d12, c22, c22, m);
add_strassen(a21, a22, d11, m);
mul_strassen(d11, b11, d12, d21, m);
add_strassen(d12, c21, c21, m);
sub_strassen(c22, d12, c22, m);
add_strassen(a11, a22, d11, m);
add_strassen(b11, b22, d12, m);
mul_strassen(d11, d12, d21, d22, m);
add_strassen(d21, c11, c11, m);
add_strassen(d21, c22, c22, m);
}
}
void print_matrix(matrix a,int n)
{
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
cout<<a[i][j]<<"\t";
cout<<endl;
}
}
int least_power_of_two(int n )
{
int i = 1, k = 1;
if (n==1)
return (0);
while ((k <<= 1) < n)
i++;
return(i);
}
void readMatrix(matrix a,int n)
{
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
cin>>a[i][j];
}
void main()
{
int n;

fatyma
یک شنبه 30 اردیبهشت 1386, 16:39 عصر
/************************************************** ************************
************************************************** ************************
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 ---------------------------//
/************************************************** ***********************/
/************************************************** ***********************/

farzad_delshad
پنج شنبه 30 خرداد 1387, 00:54 صبح
همه ما با تعریف ضرب ماتریسهای مربعی آشنایی داریم. حاصلضرب ماتریسهای مربعی A و B به صورت زیر تعریف می شه:


http://www.aachp.ir/images/91-1.gif


یه عنوان مثال در حالت n = 2 داریم:


http://www.aachp.ir/images/91-2.gif

همونطور که می بینید برای محاسبه هر درایه نیاز به n عمل ضرب داریم. بنابراین برای محاسبه تمامی n2 درایه ماتریس C به n3 عمل ضرب نیاز خواهیم داشت.
قبل از ادامه بحث به مثال زیر توجه کنید:


http://www.aachp.ir/images/91-3.gif


این مثال نشون می ده که اضافه کردن سطرها و ستونهای صفر به ماتریس تاثیری در جواب نهایی حاصلضرب نداره. (البته این مطلب رو می شه به صورت منطقی و عبارات ریاضی هم اثبات کرد.)
حالا فرض کنید مقدار n توانی از عدد 2 باشه (اگه اینطور نبود با اضافه کردن تعداد مناسبی از سطرها و ستونهای صفر مرتبه ماتریسها رو به توانی از عدد 2 می رسونیم). هر کدوم از ماتریسهای A و B رو به چهار زیر ماتریس به فرم زیر تقسیم می کنیم:


http://www.aachp.ir/images/91-4.gif

به راحتی می شه ثابت کرد همواره داریم:


http://www.aachp.ir/images/91-5.gif

اما آیا این تقسیم بندی تاثیری در بهینه شدن تعداد محاسبات داره؟
فرض کنیم ( T ( n تعداد ضربهای لازم برای محاسبه حاصلضرب این دو ماتریس - با استفاده از زیرماتریسها - رو نشون بده. پس داریم:


http://www.aachp.ir/images/91-6.gif

با حل این رابطه بازگشتی به نتیجه زیر می رسیم:


http://www.aachp.ir/images/91-7.gif

که نشون می ده همچنان n3 عمل ضرب برای محاسبه حاصلضرب نیاز هست.
ولکر استراسن با بررسی هایی که انجام داد الگوریتمی برای ضرب ماتریسها با استفاده از تقسیم بندی ارائه داد که به جای هشت عمل ضرب در هر مرحله، هفت عمل نیاز هست. به این ترتیب داریم:


http://www.aachp.ir/images/91-8.gif

مثلا اگه n برابر 1024 باشه:


http://www.aachp.ir/images/91-9.gif

یعنی در این حالت زمان محاسبه حاصلضرب به روش استراسن نسبت به حالت عادی نزدیک به چهار برابر کمتر می شه!
و اما روش استراسن:
در این روش ماتریسهای زیر که همه از مرتبه n / 2 هستن از روی زیر ماتریسهای ماتریسهای A و B ساخته می شن:


http://www.aachp.ir/images/91-10.gif

استراسن ثابت کرده زیرماتریسهای متناظر ماتریس حاصلضرب از رابطه های زیر به دست می یان:


http://www.aachp.ir/images/91-11.gif

همونطور که مشاهده می کنید تنها 7 عمل ضرب در هر مرحله برای محاسبه نیاز هست. تقسیم کردن ماتریسها به چهار بخش - برای محاسبه به روش استراسن - تا زمانی ادامه پیدا می کنه که مرتبه ماتریسها به 2 برسن. وقتی به این مرحله رسیدیم با تعریف اصلی ضرب ماتریسها حاصلضرب رو محاسبه می کنیم.

لینک برنامه http://racleon.persiangig.ir/Project/project.zip

powerboy2988
شنبه 16 آذر 1387, 21:10 عصر
الگوریتم استراسن به زبان ساده



#include <stdio.h>
#define MAX 64
typedef unsigned int n_matrix[MAX][MAX];
void compute(int n,n_matrix A,n_matrix B,n_matrix C)
{
for(int i=0;i < n;i++)
for(int j=0;j < n;j++)
{
C[i][j] = 0;
for(int k=0;k < n;k++)
C[i][j] = C[i][j] + A[i][k] * B[k][j];
}
}
void sum(n_matrix A,n_matrix B,n_matrix C)
{
for(int i=0;i < MAX;i++)
for(int j=0;j < MAX;j++)
C[i][j] = A[i][j] + B[i][j];
}
void sub(n_matrix A,n_matrix B,n_matrix C)
{
for(int i=0;i < MAX;i++)
for(int j=0;j < MAX;j++)
C[i][j] = A[i][j] - B[i][j];
}
void strassen(int n,n_matrix A,n_matrix B,n_matrix C)
{
int i,j;
if(n <= 2)
compute(n,A,B,C);
else
{
n_matrix A11,A12,A21,A22;
n_matrix B11,B12,B21,B22;
n_matrix M1 ,M2 ,M3 ,M4 ,M5 ,M6 ,M7;
for(i=0;i < n / 2;i++)
for(j=0;j < n / 2;j++)
{
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];
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];
}
n_matrix t1 ,t2;
sum(A11,A22,t1);
sum(B11,B22,t2);
strassen(n / 2,t1,t2,M1);
sum(A21,A22,t1);
strassen(n / 2,t1,B11,M2);
sub(B12,B22,t1);
strassen(n / 2,A11,t1,M3);
sub(B21,B11,t1);
strassen(n / 2,A22,t1,M4);
sum(A11,A12,t1);
strassen(n / 2,t1,B22,M5);
sub(A21,A11,t1);
sum(B11,B12,t2);
strassen(n / 2,t1,t2,M6);
sub(A12,A22,t1);
sum(B21,B22,t2);
strassen(n / 2,t1,t2,M7);
sum(M1,M4,t1);
sub(t1,M5,t1);
sum(t1,M7,t1);
sum(M3,M5,t2);
n_matrix t3,t4;
sum(M2,M4,t3);
sum(M1,M3,t4);
sub(t4,M2,t4);
sum(t4,M6,t4);
for(i=0;i < n / 2;i++)
for(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];
}
}
}
void print_matrix(n_matrix A,int n)
{
for(int i=0;i < n;i++)
{
for(int j=0;j < n;j++)
printf("%3d ",A[i][j]);
printf("\n");
}
}
void read_matrix(n_matrix A,int n)
{
for(int i=0;i < n;i++)
for(int j=0;j < n;j++)
{
printf("(%d,%d) : ",i,j);
scanf("%d",&A[i][j]);
}
}
void main(void)
{
int n;
n_matrix A,// = {{1,2,3,4},{5,6,7,8},{9,1,2,3},{4,5,6,7}},
B,// = {{8,9,1,2},{3,4,5,6},{7,8,9,1},{2,3,4,5}},
C;

printf("Please Enter Matrix Dimensions : ");
scanf("%d",&n);
printf("Please Enter Matrix A : \n");
read_matrix(A,n);
printf("Please Enter Matrix B : \n");
read_matrix(B,n);

printf("-------------------------\n");
printf("Normal Algorithm\n");
compute(n,A,B,C);
print_matrix(C,n);
printf("-------------------------\n");
printf("Strasen Algorithm\n");
strassen(n,A,B,C);
print_matrix(C,n);
}

مسعود اقدسی فام
جمعه 28 آبان 1389, 07:39 صبح
الگوریتم ضرب استراسن به صورت بازگشتی رو لطف کنید بمن بدید.:متفکر:

توضیحاتش رو می‌تونید از این پیوند مطالعه کنید:



www.labod.ir/algorithms/post.aspx?no=16 (http://www.labod.ir/algorithms/post.aspx?no=16)



کدش رو هم ظاهرا این پایین قرار دادن. نخوندمش ببینم چطوریه.