Thread: need some help , confused!

  1. #16
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Well, yes. The if is always true, since n == 0 and MatrixSize is presumably positive. Therefore no call to Strassen is made, and the clock values aren't filled out.

  2. #17
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    497
    Quote Originally Posted by tabstop View Post
    Well, yes. The if is always true, since n == 0 and MatrixSize is presumably positive. Therefore no call to Strassen is made, and the clock values aren't filled out.
    yeah , i just got it! how stupid of me !
    gotta get relaxed and try again .××)
    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


  3. #18
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    497
    i tried this (look at the bottom of Strassen()) , dont know if im doing it right ( i mean whether i should place it there or not!)
    Code:
    //بسم الله الرحمن الرحیم
    //Strassen Algorithm Impementation in C++
    //Seyyed Hossein Hasan pour
    //Release date May 5 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);
    int ADD(int** MatrixA, int** MatrixB, int** MatrixResult, int length );
    int SUB(int** MatrixA, int** MatrixB, int** MatrixResult, int length );
    int 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());
           
            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(N,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;
    }
    
    int Strassen(int N, int **MatrixA, int **MatrixB, int **MatrixC)
    {
            int HalfSize = N/2;
            
            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;
    
            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];
                    }
                }
    			for (int i = 0; i < N/2; 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
    
        //MatrixC;
    		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() %9999999);
                //matrix2[row][column] = rand() % 2;//ba hazfe in khat 50% afzayeshe soorat khahim dasht
            }
    
        }
    }
    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. #19
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    As it stands, the delete shouldn't be in the else, because they get allocated regardless of which branch in that if you take. If they get allocated regardless, they need to be deleted regardless.

    Having said that, the "right" answer is almost certainly to put the memory allocation (all the new calls) inside the else is well, so that no memory is allocated if it isn't needed.

  5. #20
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Have you considered the use of abstraction (e.g., use a matrix class) to simplify your code, including the use of RAII?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #21
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    497
    Quote Originally Posted by tabstop View Post
    As it stands, the delete shouldn't be in the else, because they get allocated regardless of which branch in that if you take. If they get allocated regardless, they need to be deleted regardless.

    Having said that, the "right" answer is almost certainly to put the memory allocation (all the new calls) inside the else is well, so that no memory is allocated if it isn't needed.
    Thank you so much for your time and your help dear tabstop .i really appreciate it
    i did this too, but still no luck
    Code:
    int Strassen(int N, int **MatrixA, int **MatrixB, int **MatrixC)
    {
            int HalfSize = N/2;
            
            
            if ( N == 2 )
            {
                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;
    
    			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];
    
    
    			}
                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];
                    }
                }
    			for (int i = 0; i < N; 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
    
        //MatrixC;
    		return 0;
    }
    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


  7. #22
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    497
    Quote Originally Posted by laserlight View Post
    Have you considered the use of abstraction (e.g., use a matrix class) to simplify your code, including the use of RAII?
    excuse me i didnt see your post at first .
    no , what is RAII ?
    and how a matrix class would avoid me getting such error! ?
    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. #23
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Masterx
    no , what is RAII ?
    A technique whereby the lifetime of a resource is tied to the lifetime of an object. In this case, you would create a Matrix class such that Matrix objects manage their own memory through correct implementation of constructors, copy constructor, copy assignment operator and destructor. You might take advantage of std::vector too.

    Consequently, when you implement the algorithm, you need not be concerned with memory management.

    Quote Originally Posted by Masterx
    and how a matrix class would avoid me getting such error! ?
    I am not sure what is the error that you are talking about, but the point is that abstraction helps you to reason about the problem by allowing you to better selectively ignore details that are unnecessary for the problem at hand.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #24
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    497
    Quote Originally Posted by laserlight View Post
    A technique whereby the lifetime of a resource is tied to the lifetime of an object. In this case, you would create a Matrix class such that Matrix objects manage their own memory through correct implementation of constructors, copy constructor, copy assignment operator and destructor. You might take advantage of std::vector too.

    Consequently, when you implement the algorithm, you need not be concerned with memory management.


    I am not sure what is the error that you are talking about, but the point is that abstraction helps you to reason about the problem by allowing you to better selectively ignore details that are unnecessary for the problem at hand.
    Thank you thats a nice idea ,
    by error i meant (allocation failure in my case here ).
    and i've already thought about vectors, im not that fluent in terms of working with it so for now i put it aside, and also the fact that i want to overcome this memory allocation failure , i might be able to flee now using that matrix class, but surely i will encounter the same problem in my next projects working on dynamic memory allocations , so i want to find a way to correct this, if possible, and if it is not possible seek other ways .
    again thank you very much dear laiserlight.
    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. #25
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Masterx
    by error i meant (allocation failure in my case here ).
    and i've already thought about vectors, im not that fluent in terms of working with it so for now i put it aside, and also the fact that i want to overcome this memory allocation failure , i might be able to flee now using that matrix class, but surely i will encounter the same problem in my next projects working on dynamic memory allocations , so i want to find a way to correct this, if possible, and if it is not possible seek other ways .
    RAII is a conventional way to deal with dynamic memory allocation in C++. Using your lack of familiarity with the standard containers as an excuse to avoid using them means that you will never become familiar with them. Basically, my line of thinking is that when you are able to see more clearly the lifetime of the matrices that you are dealing with, you will be better equipped to avoid creating matrices when you don't need them, and thus avoid over-allocation that perhaps led to allocation failure.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #26
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    497
    Quote Originally Posted by laserlight View Post
    RAII is a conventional way to deal with dynamic memory allocation in C++. Using your lack of familiarity with the standard containers as an excuse to avoid using them means that you will never become familiar with them. Basically, my line of thinking is that when you are able to see more clearly the lifetime of the matrices that you are dealing with, you will be better equipped to avoid creating matrices when you don't need them, and thus avoid over-allocation that perhaps led to allocation failure.
    yes you are absolutely right . i didnt think about it that way .
    then i think, this puts a stop to this thread .
    thanks again .
    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. #27
    بابلی ریکا Masterx's Avatar
    Join Date
    Nov 2007
    Location
    Somewhere nearby,Who Cares?
    Posts
    497
    i finally understood where the problem was , and corrected it :
    it was the base condition for my recrusive call .!
    Code:
     if ( N == 2 )
            {
                MUL(MatrixA,MatrixB,MatrixC,N);
            }
    it must be N<= 'sth' . and a very important matter that i completely forgot was that the input was supposed to be a number of power two ( 2,4,8,16,32,...512,and etc)
    and that would solve everything .

    one interesting thing that i found , was that at first when my threshold ( N) was set this way ( N<=2) , the Strassen Algorithm was way tooo slower than the conventional method! e.g multiplying two 512 *512 matrices , in conventional method would take 2 seconds while , using the Strassen it would take more than 300 seconds.
    after testing more and more, i found out thats all because of the threshold , and thus changed it to 64(N<=64) and it flated out the conventional method .
    multiplying two 1024*1024 matrices using conventional method would take 14+seconds while using Strassen it would only take 3 seconds to complete the multiplication .

    anyway. here is the final code .
    and oh before reading that . i want any of you to do me a favor , i explained how we make multidimentional arrays in C++, please read that part , and tell me my mistakes .
    That will be a great help for me in understanding the concepts .
    Thank you all in advance
    Code:
    //بسم الله الرحمن الرحیم
    /*
    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 : [email protected]
    YM    : [email protected]
    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;
    
    }
    /*
    in order to be able to create a matrix without any limitaion in c++,
    one way is to create it using pointers.
    as you see by using a pointer to pointer strategy we can make a multi-
    dimensional Matrix of any size . The notation also makes us capable of
    creating a matrix with VARIABLE size at runtime ,meaning we can resize
    the size of our matrix at runtime , shrink it or increase it , your choice.
    what we do is simple , first we make a pointer of pointer variable , this
    means that our first pointer will point to another pointer which again
    this pointer ,points to sth else(we can make it point to an array) .
    int **A;
    will declare the variable , we now need to expand it .
    now make a pointer based array and allocate the memory dynamicly
    
    A = new int *[desired_array_row];
    
    this gives us a one diminsional pointer based array,now you want a 2D array?
    big deal,lets make one.
    we use for() to achieve this goal , remember when i said we are going to make
    a variable which is a pointer of pointer ? which meant any location pointed to somewhere else
    , we made a pointer based array , a one diminsional one , just up there ,
    and you know this fatct that an array is consits of individual blocks right?
    and the fact that each block can be used just like a solo variable.
    so simply if we could write
    A = new int *[any_size];
    cant we do it to all of our indiviual array blocks which are just like the solo variable ?
    so this means that if we could do it with A, and get an array , we can use the same method
    to make different arrays for different block of the array we made in first place.
    we use for() to iterate through all of the blocks of the previously made array, and
    then for each block we create a single array .
    
    for ( int i = 0; i < desired_array_row; i++)
    A[i] = new int [desired_column_size];
    
    after this for , we can enjoy our 2D array wich can be access like any ordinary array we know.
    just use the conventional notation for accessing array blocks for either reading or writing.( A[i][j])
    and remember to free the space we allocated for our 2D array at the end of the program .
    we do such a thing this way:
    
    for ( int i = 0; i < your_array_row; i++)
    {
        delete [] A[i];
    }
    delete[] A;
    
    .using this method you can make any N-diminsional array, you just need to use for with right iteration.
    
    
    
    */
    int Strassen(int N, int **MatrixA, int **MatrixB, int **MatrixC)
    {
    
            int HalfSize = N/2;
            int newSize = N/2;
    
            if ( N <= 64 )//choosing the threshhold is extremely important, try N<=2 to see the result
            {
                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;
    }
    Last edited by Masterx; 05-09-2010 at 12:27 PM.
    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


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, 05: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, 05: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