تبلیغات
Linux warez Download,Software,Ebook, Graphic,,|مرجع دنلود وآموزشهای تخصصی گرافیک و برنامه نویسی - پیاده سازی الگوریتم استراسن در سی پلاس پلاس

Linux warez Download,Software,Ebook, Graphic,,|مرجع دنلود وآموزشهای تخصصی گرافیک و برنامه نویسی

دوشنبه 20 اردیبهشت 1389

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

نویسنده: Master   طبقه بندی: Programming Tutorials، Source Codes Center، 

سلام به همگی . 
این هم از سورس کدکامل الگوریتم استراسن که قراربود بعد از نوشتنش در اختیار همه دوستان قرار بدم . 
توضیحات فارسی رو هم نوشتم البته یه سری جاها انگلیسیه هنوز که اینم دلیل داره . دلیلش هم سایتهای مثل planet-sourcecode هست که کدها رو اونجا برای استفاده بقیه قرار میدم و همچنین n جای دیگه :دی
فی الحال دوستان اینو ببینن هر جا که متوجه نشدن بگن تا من توضیح بدم . 
دنلود پروژه و سورس کد 

(برای دیدن خود سورس کد بدون دنلود کردن هم به ادامه مطلب ارائه کنید)

بسم الله الرحمن الرحیم
/*
Strassen Algorithm Implementation in C++
Coded By: Seyyed Hossein Hasan Pour MatiKolaee in May 5 2010 .
Mazandaran University of Science and Technology,Babol,Mazandaran,Iran
--------------------------------------------
Email : Master.huricane@gmail.com
YM : Deathmaster_nemessis@yahoo.com
Updated may 09 2010.
*/
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <ctime>
#include <windows.h>
using namespace std;

int Strassen(int n, int** MatrixA, int ** MatrixB, int ** MatrixC);//Multiplies Two Matrices recrusively.
int ADD(int** MatrixA, int** MatrixB, int** MatrixResult, int length );//Adds two Matrices, and places the result in another Matrix
int SUB(int** MatrixA, int** MatrixB, int** MatrixResult, int length );//subtracts two Matrices , and places the result in another Matrix
int MUL(int** MatrixA, int** MatrixB, int** MatrixResult, int length );//Multiplies two matrices in conventional way.
void FillMatrix( int** matrix1, int** matrix2, int length);//Fills Matrices with random numbers.
void PrintMatrix( int **MatrixA, int MatrixSize );//prints the Matrix content.

int main()
{

int MatrixSize = 0;

int** MatrixA;
int** MatrixB;
int** MatrixC;

clock_t startTime_For_Normal_Multipilication ;
clock_t endTime_For_Normal_Multipilication ;

clock_t startTime_For_Strassen ;
clock_t endTime_For_Strassen ;

time_t start,end;

srand(time(0));

cout<<setw(45)<<"In the name of GOD";
cout<<endl<<setw(60)<<"Strassen Algorithm Implementation in C++ "
<<endl<<endl<<setw(50)<<"By Seyyed Hossein Hasan Pour"
<<endl<<setw(60)<<"Mazandaran University of Science and Technology"
<<endl<<setw(40)<<"May 9 2010";

cout<<"\nPlease Enter your Matrix Size(must be in a power of two(eg:32,64,512,..): ";
cin>>MatrixSize;

int N = MatrixSize;//for readiblity.


MatrixA = new int *[MatrixSize];
MatrixB = new int *[MatrixSize];
MatrixC = new int *[MatrixSize];

for (int i = 0; i < MatrixSize; i++)
{
MatrixA[i] = new int [MatrixSize];
MatrixB[i] = new int [MatrixSize];
MatrixC[i] = new int [MatrixSize];
}

FillMatrix(MatrixA,MatrixB,MatrixSize);

//*******************conventional multiplication test
cout<<"Phase I started: "<< (startTime_For_Normal_Multipilication = clock());

MUL(MatrixA,MatrixB,MatrixC,MatrixSize);

cout<<"\nPhase I ended: "<< (endTime_For_Normal_Multipilication = clock());

//cout<<"\nMatrix Result... \n";
//PrintMatrix(MatrixC,MatrixSize);

//*******************Strassen multiplication test
cout<<"\nMultiplication started: "<< (startTime_For_Strassen = clock());

Strassen( N, MatrixA, MatrixB, MatrixC );

cout<<"\nMultiplication: "<<(endTime_For_Strassen = clock());


cout<<"\nMatrix Result... \n";
//PrintMatrix(MatrixC,MatrixSize);

cout<<"Matrix size "<<MatrixSize;
cout<<"\nNormal mode "<<(endTime_For_Normal_Multipilication - startTime_For_Normal_Multipilication)<<" Clocks.."<<(endTime_For_Normal_Multipilication - startTime_For_Normal_Multipilication)/CLOCKS_PER_SEC<<" Sec";
cout<<"\nStrassen mode "<<(endTime_For_Strassen - startTime_For_Strassen)<<" Clocks.."<<(endTime_For_Strassen - startTime_For_Strassen)/CLOCKS_PER_SEC<<" Sec\n";
system("Pause");
return 0;

}
/*
بسم الله الرحمن الرحیم
اولین مصیبتی که یک فرد در سی++باهاش مواجه میشه محدودیت مشخص کردن اندازه آرایه و تعیین اندازه آرایه در زمان اجراست
البته دومین مشکل در اسناندارد سی99 زبان سی++حل شده اما همه کامپایلرها هنوز از اون بصورت کامل پشتیبانی نمیکنن
دومین مشکل بخاطر اندازه استک هست . یه راه حلی هست که میتونه تا حدی این محدودیت اندازه آرایه رو برداره
و اون اینه که متغییرتون یا آرایتون رو بجای اینکه محلی تعریف کنید گلوبال یا سراسری تعریف کنید .
یعنی ببریدش بالای فانکشن مین تعریف کنید .
اینجوری دستتون خیلی بازتر از قبل میشه . اما هنوز محدودیت وجود داره .
اما برای رفع این محدودیت هم ما دو راه داریم .
یا از کلاس وکتور در سی++استفاده کنیم که کلا خیلی خوبه و محدودیتی نداره .
دوم از همون اشاره گرهای سابق استفاده کنیم .
برای اینکه در سی ++بتونیم آرایه با اندازه متغییر داشته باشیم از اشارگرها استفاده میکنیم
دستور زیر یک متغیر از نوع اشاره گر به اشاره گر اینت تعریف میکنه
int **A;
چرا دوتا اشاره گر ؟
چون قرار ما یه آرایه دو بعدی داشته باشیم . یعنی در اصل دوتا آرایه یک بعدی
حالا اگه قرار باشه اینو بسطش بدیم
ابتدا باید آرایه اولیه رو بسازیم .
(قضیه از این قراره که ما اول یه آرایه میسازیم . بعد برای هر خونه این آرایه باز یک آرایه دیکه تعریف
میکنیم . که اینجوری میشه یه آرایه دوبعدی
نحوه انجامشم اینطوریه تو سی++
دستور زیر اون آرایه یک بعدی که بالا گفتم رو برامون میسازه
A = new int *[تعداد سطرهای آرایه شما];
از اونجایی که هر خونه آرایه دقیقا عین هم هستند و وقتی ما تونستیم برای یه دونه متغییر یه آرایه
مبتی بر اشارهگر ها بسازیم . پس برای هر خونه آرایه هم میشه همین کار رو تکرار کرد .
اینجوری این کار رو انجام میدیم .
از یه حلقه فور استفاده میکنیم و برای تک تک خونه های آرایه یه آرایه اختصاص میدیم .

for ( int i = 0; i < تعداد سطرهای آرایه شما; i++)
A[i] = new int [تعداد ستون های دلخواه شما];
با همین دوتا دستور ما الان یه ارایه دوبعدی داریم که میتونیم خیلی راحتی مثل یه آرایه معمولی دو بعدی بهش دسترسی داشته باشیم
A[i][j];
از دستور new
هم استفاده کردیم تا بصورت داینامیک فضا اختصاص بده .با این کار میتونیم اندازه آرایه مون رو در زمان اجرا
کم و یا زیاد کنیم .

در آخر هم یادتون باشه که فضایی که در اختیار گرفتیم رو آزاد کنیم .
for ( int i = 0; i < اندازه آرایه(سطر); i++)
{
delete [] A[i];
}
delete[] A;

بقیه الگوریتم که کشکی بود مشخصه .
فقط یه نکنه خیلی ظریف داره اشاره کردم . پایین

*/
int Strassen(int N, int **MatrixA, int **MatrixB, int **MatrixC)
{

int HalfSize = N/2;
int newSize = N/2;
//اینجاست که خیلی مهمه .خودتون این عدد رو عوض کنید برنامه رو اجرا کنید و نتیجه رو خودتون ببنید . جالبه.همین
//نکته منو چند ساعتی معطل خودش کرد که چرا الگوریتم استراسن عوض سریعتر بودن کند تره!!
if ( N <= 64 )
{
MUL(MatrixA,MatrixB,MatrixC,N);
}
else
{
int** A11;
int** A12;
int** A21;
int** A22;

int** B11;
int** B12;
int** B21;
int** B22;

int** C11;
int** C12;
int** C21;
int** C22;

int** M1;
int** M2;
int** M3;
int** M4;
int** M5;
int** M6;
int** M7;
int** AResult;
int** BResult;

//making a 1 diminsional pointer based array.
A11 = new int *[newSize];
A12 = new int *[newSize];
A21 = new int *[newSize];
A22 = new int *[newSize];

B11 = new int *[newSize];
B12 = new int *[newSize];
B21 = new int *[newSize];
B22 = new int *[newSize];

C11 = new int *[newSize];
C12 = new int *[newSize];
C21 = new int *[newSize];
C22 = new int *[newSize];

M1 = new int *[newSize];
M2 = new int *[newSize];
M3 = new int *[newSize];
M4 = new int *[newSize];
M5 = new int *[newSize];
M6 = new int *[newSize];
M7 = new int *[newSize];

AResult = new int *[newSize];
BResult = new int *[newSize];

int newLength = newSize;

//making that 1 diminsional pointer based array , a 2D pointer based array
for ( int i = 0; i < newSize; i++)
{
A11[i] = new int[newLength];
A12[i] = new int[newLength];
A21[i] = new int[newLength];
A22[i] = new int[newLength];

B11[i] = new int[newLength];
B12[i] = new int[newLength];
B21[i] = new int[newLength];
B22[i] = new int[newLength];

C11[i] = new int[newLength];
C12[i] = new int[newLength];
C21[i] = new int[newLength];
C22[i] = new int[newLength];

M1[i] = new int[newLength];
M2[i] = new int[newLength];
M3[i] = new int[newLength];
M4[i] = new int[newLength];
M5[i] = new int[newLength];
M6[i] = new int[newLength];
M7[i] = new int[newLength];

AResult[i] = new int[newLength];
BResult[i] = new int[newLength];


}
//splitting input Matrixes, into 4 submatrices each.
for (int i = 0; i < N / 2; i++)
{
for (int j = 0; j < N / 2; j++)
{
A11[i][j] = MatrixA[i][j];
A12[i][j] = MatrixA[i][j + N / 2];
A21[i][j] = MatrixA[i + N / 2][j];
A22[i][j] = MatrixA[i + N / 2][j + N / 2];

B11[i][j] = MatrixB[i][j];
B12[i][j] = MatrixB[i][j + N / 2];
B21[i][j] = MatrixB[i + N / 2][j];
B22[i][j] = MatrixB[i + N / 2][j + N / 2];

}
}

//here we calculate M1..M7 matrices .
//M1[][]
ADD( A11,A22,AResult, HalfSize);
ADD( B11,B22,BResult, HalfSize);
Strassen( HalfSize, AResult, BResult, M1 ); //now that we need to multiply this , we use the strassen itself .


//M2[][]
ADD( A21,A22,AResult, HalfSize); //M2=(A21+A22)B11
Strassen(HalfSize, AResult, B11, M2); //Mul(AResult,B11,M2);

//M3[][]
SUB( B12,B22,BResult, HalfSize); //M3=A11(B12-B22)
Strassen(HalfSize, A11, BResult, M3); //Mul(A11,BResult,M3);

//M4[][]
SUB( B21, B11, BResult, HalfSize); //M4=A22(B21-B11)
Strassen(HalfSize, A22, BResult, M4); //Mul(A22,BResult,M4);

//M5[][]
ADD( A11, A12, AResult, HalfSize); //M5=(A11+A12)B22
Strassen(HalfSize, AResult, B22, M5); //Mul(AResult,B22,M5);


//M6[][]
SUB( A21, A11, AResult, HalfSize);
ADD( B11, B12, BResult, HalfSize); //M6=(A21-A11)(B11+B12)
Strassen( HalfSize, AResult, BResult, M6); //Mul(AResult,BResult,M6);

//M7[][]
SUB(A12, A22, AResult, HalfSize);
ADD(B21, B22, BResult, HalfSize); //M7=(A12-A22)(B21+B22)
Strassen(HalfSize, AResult, BResult, M7); //Mul(AResult,BResult,M7);

//C11 = M1 + M4 - M5 + M7;
ADD( M1, M4, AResult, HalfSize);
SUB( M7, M5, BResult, HalfSize);
ADD( AResult, BResult, C11, HalfSize);

//C12 = M3 + M5;
ADD( M3, M5, C12, HalfSize);

//C21 = M2 + M4;
ADD( M2, M4, C21, HalfSize);

//C22 = M1 + M3 - M2 + M6;
ADD( M1, M3, AResult, HalfSize);
SUB( M6, M2, BResult, HalfSize);
ADD( AResult, BResult, C22, HalfSize);


//at this point , we have calculated the c11..c22 matrices, and now we are going to
//put them together and make a unit matrix which would describe our resulting Matrix.
for (int i = 0; i < N/2 ; i++)
{
for (int j = 0 ; j < N/2 ; j++)
{
MatrixC[i][j] = C11[i][j];
MatrixC[i][j + N / 2] = C12[i][j];
MatrixC[i + N / 2][j] = C21[i][j];
MatrixC[i + N / 2][j + N / 2] = C22[i][j];
}
}

// dont forget to free the space we alocated for matrices,
for (int i = 0; i < newLength; i++)
{
delete[] A11[i];delete[] A12[i];delete[] A21[i];
delete[] A22[i];

delete[] B11[i];delete[] B12[i];delete[] B21[i];
delete[] B22[i];
delete[] C11[i];delete[] C12[i];delete[] C21[i];
delete[] C22[i];
delete[] M1[i];delete[] M2[i];delete[] M3[i];delete[] M4[i];
delete[] M5[i];delete[] M6[i];delete[] M7[i];
delete[] AResult[i];delete[] BResult[i] ;
}
delete[] A11;delete[] A12;delete[] A21;delete[] A22;
delete[] B11;delete[] B12;delete[] B21;delete[] B22;
delete[] C11;delete[] C12;delete[] C21;delete[] C22;
delete[] M1;delete[] M2;delete[] M3;delete[] M4;delete[] M5;
delete[] M6;delete[] M7;
delete[] AResult;
delete[] BResult ;


}//end of else


return 0;
}

int ADD(int** MatrixA, int** MatrixB, int** MatrixResult, int MatrixSize )
{
for ( int i = 0; i < MatrixSize; i++)
{
for ( int j = 0; j < MatrixSize; j++)
{
MatrixResult[i][j] = MatrixA[i][j] + MatrixB[i][j];
}
}
return 0;
}

int SUB(int** MatrixA, int** MatrixB, int** MatrixResult, int MatrixSize )
{
for ( int i = 0; i < MatrixSize; i++)
{
for ( int j = 0; j < MatrixSize; j++)
{
MatrixResult[i][j] = MatrixA[i][j] - MatrixB[i][j];
}
}
return 0;
}

int MUL( int** MatrixA, int** MatrixB, int** MatrixResult, int MatrixSize )
{
for (int i=0;i<MatrixSize ;i++)
{
for (int j=0;j<MatrixSize ;j++)
{
MatrixResult[i][j]=0;
for (int k=0;k<MatrixSize ;k++)
{
MatrixResult[i][j]=MatrixResult[i][j]+MatrixA[i][k]*MatrixB[k][j];
}
}
}
return 0;
}

void FillMatrix( int** MatrixA, int** MatrixB, int length)
{
for(int row = 0; row<length; row++)
{
for(int column = 0; column<length; column++)
{

MatrixB[row][column] = (MatrixA[row][column] = rand() %5);
//matrix2[row][column] = rand() % 2;//ba hazfe in khat 50% afzayeshe soorat khahim dasht
}

}
}
void PrintMatrix(int **MatrixA,int MatrixSize)
{
cout<<endl;
for(int row = 0; row<MatrixSize; row++)
{
for(int column = 0; column<MatrixSize; column++)
{


cout<<MatrixA[row][column]<<"\t";
if ((column+1)%((MatrixSize)) == 0)
cout<<endl;
}

}
cout<<endl;
}

نظرات() 
How do you get a growth spurt?
دوشنبه 30 مرداد 1396 10:44 ق.ظ
Currently it sounds like Drupal is the top blogging platform out there right now.

(from what I've read) Is that what you're using on your blog?
Foot Pain
دوشنبه 16 مرداد 1396 09:42 ب.ظ
Actually no matter if someone doesn't be aware of afterward its up to other visitors that they will assist, so here it takes place.
Do you get taller when you stretch?
دوشنبه 16 مرداد 1396 02:49 ب.ظ
This is very interesting, You're a very skilled blogger.
I've joined your feed and look forward to seeking more of your
magnificent post. Also, I have shared your website
in my social networks!
sinceredevil4815.sosblogs.com
پنجشنبه 21 اردیبهشت 1396 08:40 ق.ظ
As the admin of this web page is working, no
question very rapidly it will be famous, due to its feature contents.
BHW
پنجشنبه 31 فروردین 1396 02:09 ق.ظ
My family always say that I am killing my time here at web, but I know I
am getting know-how all the time by reading such fastidious articles or
reviews.
manicure
دوشنبه 21 فروردین 1396 09:38 ب.ظ
I don't even know how I ended up here, but I thought this post
was great. I don't know who you are but definitely you are going to a famous blogger if you are not already ;) Cheers!
manicure
دوشنبه 14 فروردین 1396 07:05 ب.ظ
I'm not sure exactly why but this blog is loading incredibly slow for me.
Is anyone else having this issue or is it a problem on my end?
I'll check back later on and see if the problem still exists.
manicure
یکشنبه 13 فروردین 1396 07:26 ق.ظ
I seriously love your site.. Excellent colors & theme.
Did you develop this web site yourself? Please reply back as
I'm looking to create my own site and would love to know where
you got this from or exactly what the theme is called.

Cheers!
manicure
شنبه 12 فروردین 1396 03:04 ب.ظ
When someone writes an piece of writing he/she keeps the idea of
a user in his/her mind that how a user can understand
it. Thus that's why this post is perfect. Thanks!
BHW
جمعه 11 فروردین 1396 12:57 ب.ظ
Howdy! Do you use Twitter? I'd like to follow you if that
would be okay. I'm undoubtedly enjoying your blog and look forward to new updates.
 
لبخندناراحتچشمک
نیشخندبغلسوال
قلبخجالتزبان
ماچتعجبعصبانی
عینکشیطانگریه
خندهقهقههخداحافظ
سبزقهرهورا
دستگلتفکر

نویسندگان

صفحات جانبی

نظرسنجی

    Where are you from?





آمار وبلاگ

  • کل بازدید :
  • بازدید امروز :
  • بازدید دیروز :
  • بازدید این ماه :
  • بازدید ماه قبل :
  • تعداد نویسندگان :
  • تعداد کل پست ها :
  • آخرین بازدید :
  • آخرین بروز رسانی :