# need some help , confused!

Printable View

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 05-05-2010
Masterx
need some help , confused!
hello all , i've just written an implementation of Strassen algorithm , and i think i did it right! but some how im not getting the right result ,
here's the code , can you please help me find the cause of problem here?
thanks in advance
[code]//بسم الله الرحمن الرحیم
//Strassen Algorithm Impementation in C++
[code]//Seyyed Hossein Hasan pour Matikolaee
Code:

```//بسم الله الرحمن الرحیم //Strassen Algorithm Impementation in C++ //Release date May 5 2010 #include <iostream> #include <cstdlib> #include <iomanip> #include <ctime> #include <windows.h> using namespace std; void Strassen(int n, int** MatrixA, int ** MatrixB, int ** MatrixC); void ADD(int** MatrixA, int** MatrixB, int** MatrixResult, int length ); void SUB(int** MatrixA, int** MatrixB, int** MatrixResult, int length ); void MUL(int** MatrixA, int** MatrixB, int** MatrixResult, int length ); void FillMatrix( int** matrix1, int** matrix2, int length); int main() {     int n  = 0;     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<<"In the name of GOD"<<endl;     cout<<"\nPlease Enter your Matrix Size: ";     cin>>MatrixSize;     int N = MatrixSize;     cout<<"Please Enter your Threshhold: ";     cin>>n;     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);   // if ( n <= MatrixSize )     //{         cout<<"Phase I started:  "<< (startTime_For_Normal_Multipilication = clock());         //MUL(MatrixA,MatrixB,MatrixC,MatrixSize);         //{         for (int i=0;i<N;i++)         {               for (int j=0;j<N;j++)               {                   MatrixC[i][j]=0;                   for (int k=0;k<N;k++)                   {                           MatrixC[i][j]=MatrixC[i][j]+MatrixA[i][k]*MatrixB[k][j];                   }               }         }     //}         cout<<"\nPhase I ended: "<< (endTime_For_Normal_Multipilication = clock());     //}     //else     //{         cout<<"\nPhase II started: "<< (startTime_For_Strassen = clock());         Strassen(MatrixSize,MatrixA,MatrixB,MatrixC);         cout<<"\nPhase II ended: "<<(endTime_For_Strassen = clock());   // }     cout<<"\nStats:\n";     cout<<"Normal mode "<<(endTime_For_Normal_Multipilication - startTime_For_Normal_Multipilication)/CLOCKS_PER_SEC<<" Sec";     cout<<"\nStrassen mode "<<(endTime_For_Strassen - startTime_For_Strassen)/CLOCKS_PER_SEC<<" Sec";     system("Pause");     return 0; } void Strassen(int N, int** MatrixA, int** MatrixB, int** MatrixC) {         int HalfSize = N/2;         int** M1;         int** M2;         int** M3;         int** M4;         int** M5;         int** M6;         int** M7;         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** AResult;         int** BResult;         A11 = new int *[N];         A12 = new int *[N];         A21 = new int *[N];         A22 = new int *[N];         B11 = new int *[N];         B12 = new int *[N];         B21 = new int *[N];         B22 = new int *[N];         C11 = new int *[N];         C12 = new int *[N];         C21 = new int *[N];         C22 = new int *[N];         M1 = new int *[N];         M2 = new int *[N];         M3 = new int *[N];         M4 = new int *[N];         M5 = new int *[N];         M6 = new int *[N];         M7 = new int *[N];         AResult = new int *[N];         BResult = new int *[N];         for ( int i = 0; i < N; i++)         {             A11[i] = new int[N];             A12[i] = new int[N];             A21[i] = new int[N];             A22[i] = new int[N];             B11[i] = new int[N];             B12[i] = new int[N];             B21[i] = new int[N];             B22[i] = new int[N];             C11[i] = new int[N];             C12[i] = new int[N];             C21[i] = new int[N];             C22[i] = new int[N];             M1[i] = new int[N];             M2[i] = new int[N];             M3[i] = new int[N];             M4[i] = new int[N];             M5[i] = new int[N];             M6[i] = new int[N];             M7[i] = new int[N];             AResult[i] = new int[N];             BResult[i] = new int[N];         }         if ( N == 2 )         {             MUL(MatrixA,MatrixB,MatrixC,N);         }         else         {             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];                 }             }             //M1[][]             ADD( A11,A22,AResult, HalfSize);             ADD( B11,B22,BResult, HalfSize);             Strassen( HalfSize, AResult, BResult, M1 ); //Mul(AResult,BResult,M1);             //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);             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];                 }             }         }//end of else     //MatrixC; } void 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];         }     } } void 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];         }     } } void 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];                   }               }         } } 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() %9999999);             //matrix2[row][column] = rand() % 2;//ba hazfe in khat 50% afzayeshe soorat khahim dasht         }     } }```
• 05-05-2010
tabstop
I don't think MUL is what you want it to be.
• 05-05-2010
Masterx
Quote:

Originally Posted by tabstop
I don't think MUL is what you want it to be.

Thank you .
Code:

```for ( int i = 0; i < MatrixSize; i++)     {         for ( int j = 0; j < MatrixSize; j++)         {             MatrixResult[i][j] =  MatrixA[i][j] * MatrixB[i][j];         }     }```
we do multiply two matrices this way right?oO
(debugging in Codeblocks is indeed tedious , (im now installing Microsoft Visual C++ Express :( to use its debugging facility )
• 05-05-2010
tabstop
Quote:

Originally Posted by Masterx
Thank you .
we do multiply two matrices this way right?oO

Not even a little bit. You've got it right in your timing loop up above; matrix multiplication hasn't changed from the top of the program to the bottom....
• 05-05-2010
Masterx
Quote:

Originally Posted by tabstop
Not even a little bit. You've got it right in your timing loop up above; matrix multiplication hasn't changed from the top of the program to the bottom....

thanks again , corrected the MUL function(Multiplication function) .
again i'm getting a segmentation error ! and thats in Strassen function!
i didt precisly get what you just mentioned by saying "
Quote:

matrix multiplication hasn't changed from the top of the program to the bottom"
• 05-05-2010
tabstop
If you're getting a segmentation fault, run it in gdb and let it crash, then use bt and some print statements to see what's going on when it crashes.

For sure, you're allocating a large amount of memory that you don't need (all those submatrices should be of size N/2), and nothing ever gets delete[]d....
• 05-05-2010
Masterx
if i input the application ranging from 1 to 20, it doesnt crash , but when i input 30 or more, i get the message "
Unhandled exception at 0x7c81eb33 in Matrix.exe: Microsoft C++ exception: std::bad_alloc at memory location 0x00033704.."
in visual C++ express 2008 , and it points to
Code:

`A11 = new int *[N];`
where i'm allocating memory for A11 .
why is it hapening?
• 05-05-2010
tabstop
std::bad_alloc == "out of memory"
• 05-05-2010
Masterx
Quote:

Originally Posted by tabstop
If you're getting a segmentation fault, run it in gdb and let it crash, then use bt and some print statements to see what's going on when it crashes.

For sure, you're allocating a large amount of memory that you don't need (all those submatrices should be of size N/2), and nothing ever gets delete[]d....

they are called recursively if i delete them at the end of the function would it not mess everything ?
and about the size , i guess you are right , those A,B and c are submatrices and they dont need to have that much space , then Ok i reduce them to N/2, and see what happens .
( still i dont get it why would dynamic allocation fails! )
• 05-05-2010
tabstop
Quote:

Originally Posted by Masterx
they are called recursively if i delete them at the end of the function would it not mess everything ?

Of course not. Once you copy the answer into matrixC all those other matrices can go away.
• 05-05-2010
Masterx
Quote:

Originally Posted by tabstop
std::bad_alloc == "out of memory"

i reduced the size to N/2, but still im getting the same message in the exact same place as when it was N.:(
• 05-05-2010
tabstop
Did you do the deletes yet? Given that each Strassen call generates 21 new submatrices, and each one spawns seven recursive calls.... starting with a 32x32 matrix you have 50,421 matrices at the lowest level, which is quite a few, especially since I don't know how well Windows' memory management copes with small malloc sizes.
• 05-05-2010
Masterx
Quote:

Originally Posted by tabstop
Did you do the deletes yet? Given that each Strassen call generates 21 new submatrices, and each one spawns seven recursive calls.... starting with a 32x32 matrix you have 50,421 matrices at the lowest level, which is quite a few, especially since I don't know how well Windows' memory management copes with small malloc sizes.

no ,not yet actually .
well i dont know how to delete them the proper way!
would this do it ?
Code:

```for ( int i = 0; i < N ; i++) {       delete A11[i] *[N]; }```
im not sure!
• 05-05-2010
tabstop
You should have learned delete at the same time you learned new. Everything that you get from new[] must be delete[]d. So you would need to delete each row, and the main matrix as well.
Code:

```for (int i = 0; i < N/2; i++) {     delete[] A11[i]; } delete[] A11;```
• 05-05-2010
Masterx
Quote:

Originally Posted by tabstop
You should have learned delete at the same time you learned new. Everything that you get from new[] must be delete[]d. So you would need to delete each row, and the main matrix as well.
Code:

```for (int i = 0; i < N/2; i++) {     delete[] A11[i]; } delete[] A11;```

thank you verymuch , i learned it too, but due to not working with this dynamic allocation in a long time i forgot it .

Edited : huge mistake !!
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last