need some help , confused!

This is a discussion on need some help , confused! within the C++ Programming forums, part of the General Programming Boards category; hello all , i've just written an implementation of Strassen algorithm , and i think i did it right! but ...

  1. #1
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493

    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
            }
    
        }
    }
    Last edited by Masterx; 05-05-2010 at 09:42 AM.
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I don't think MUL is what you want it to be.

  3. #3
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493
    Quote Originally Posted by tabstop View Post
    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 )
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Masterx View Post
    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....

  5. #5
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493
    Quote Originally Posted by tabstop View Post
    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 "
    matrix multiplication hasn't changed from the top of the program to the bottom"
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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....

  7. #7
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493
    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?
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    std::bad_alloc == "out of memory"

  9. #9
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493
    Quote Originally Posted by tabstop View Post
    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! )
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Masterx View Post
    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.

  11. #11
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493
    Quote Originally Posted by tabstop View Post
    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.
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  13. #13
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493

    Thumbs up

    Quote Originally Posted by tabstop View Post
    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!
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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;

  15. #15
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    493
    Quote Originally Posted by tabstop View Post
    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 !!
    Last edited by Masterx; 05-05-2010 at 11:11 AM.
    Highlight Your Codes
    The Boost C++ Libraries (online Reference)

    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.."
    Bill Bryson


Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Confused with array size
    By desmond5 in forum C Programming
    Replies: 4
    Last Post: 12-04-2007, 04:14 PM
  2. New to C++ and confused by boolean and ifs and else
    By jconner in forum C++ Programming
    Replies: 10
    Last Post: 08-02-2006, 03:29 AM
  3. Confused about Memory
    By gL_nEwB in forum C++ Programming
    Replies: 22
    Last Post: 06-20-2006, 07:32 PM
  4. So Now Im getting confused?!?!?
    By zergdeath1 in forum C++ Programming
    Replies: 11
    Last Post: 03-06-2004, 04:41 PM
  5. confused.. in selecting my line of deapth
    By jawwadalam in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 05-04-2003, 01:21 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21