2
\$\begingroup\$

I'm visiting some code that I wrote for one of my finals projects and wanted to know whether there were a more optimal, more elegant way to do this so it does not look so "hard-coded".

The problem was that I needed to calculate the Determinant of a matrix, and, at the time (some of it was rushed) I did not know of a better way, using loops or re-usable code that could make the code a little better. Here is the code:

namespace Determinant {


    template<int X>
    float determinant(std::vector<Vector> &data)
    {   

        float deter = 0.0;
        if(X == 2)
        {
            float a = data[0][0]; 
            float b = data[1][0]; 
            float c = data[1][1]; 

            deter = (a + c) * (a + c) -4 * (a*c-b*b);
        }else if(X == 3)
        {   

            float determinant1 = (data[1][1] * data[2][2]) - (data[2][1] * data[1][2]); 
            float determinant2 = (data[1][0] * data[2][2]) - (data[2][0] * data[1][2]); 
            float determinant3 = (data[1][0] * data[2][1]) - (data[2][0] * data[1][1]);

            deter = (data[0][0] * determinant1) - (data[0][1] * determinant2) + (data[0][2] * determinant3);
        }
        return deter; 
    }
}

As you can see the Determinant is very hard-coded which is probably not the right way -- But are there any other alternatives that isn't hard-coded? I want to start to use a design pattern, as I feel one would be useful here but can't seem to figure out which one.

\$\endgroup\$
3
\$\begingroup\$

You don't really need a design pattern for determinants, just a better algorithm. Generally one of the easiest (and fastest) ways of calculating a matrix determinant is by using what is known as LU-Decomposition. This factors a matrix into two matrices, a lower triangular and an upper triangular matrix. From these, the determinant can simply be calculated as the product of diagonal elements.

Note that you have to be careful when calculating determinants of large matrices; for a 100x100 matrix, it can easily overflow the maximum size of a float (or double). For this reason it's often better to calculate a log-determinant.

On to the actual code you've presented:

data should be passed by const& since it isn't (and shouldn't be) modified:

float determinant(const std::vector<Vector>& data)

Using a template int parameter to choose between determinant sizes is really odd, and is potentially easily misused. What if I use Determinant::determinant<2>(...) on a 3x3 matrix? It'll give me the wrong answer. You should generally try to make your code easy to use and hard to misuse. In this case, that means calculating the determinant size based on the row/column size of the passed parameter. Better yet would be creating a matrix class to encapsulate all of this information.

These days, it generally doesn't make a lot of sense to use float over double unless you really need the speed (and even then, it is often no faster, and can sometimes even be slower on modern hardware). Stick to using double by default.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the reply. I do get your point, this algorithm isn't the best. I did look at the LU-Decomposition and this is a much better algorithm. I also get your point over float/double and will stick to double. I don't get why passing in a int X to determine the size is a bad thing? Since I can have a if statement that works well like this, are you saying that when using LU-Decomposition, there is no need to have multiple if statements etc..? \$\endgroup\$ – Phorce Feb 2 '15 at 10:53
  • \$\begingroup\$ You should just infer the size of the matrix from data.size(). There's no need for a template. \$\endgroup\$ – 200_success Feb 2 '15 at 10:59
1
\$\begingroup\$

This May Help - see comments within the code for an explanation:

static int CalcDeterminant(vector<vector<int>> Matrix)
   {
        //this function is written in c++ to calculate the determinant of matrix
        // it's a recursive function that can handle matrix of any dimension
        int det = 0; // the determinant value will be stored here
        if (Matrix.size() == 1)
        {
            return Matrix[0][0]; // no calculation needed
        }
        else if (Matrix.size() == 2)
        {
            //in this case we calculate the determinant of a 2-dimensional matrix in a 
            //default procedure
            det = (Matrix[0][0] * Matrix[1][1] - Matrix[0][1] * Matrix[1][0]);
            return det;
        }
        else
        {
            //in this case we calculate the determinant of a squared matrix that have 
            // for example 3x3 order greater than 2
            for (int p = 0; p < Matrix[0].size(); p++)
            {
                //this loop iterate on each elements of the first row in the matrix.
                //at each element we cancel the row and column it exist in
                //and form a matrix from the rest of the elements in the matrix
                vector<vector<int>> TempMatrix; // to hold the shaped matrix;
                for (int i = 1; i < Matrix.size(); i++)
                {
                    // iteration will start from row one cancelling the first row values
                    vector<int> TempRow;
                    for (int j = 0; j < Matrix[i].size(); j++)
                    {
                        // iteration will pass all cells of the i row excluding the j 
                        //value that match p column
                        if (j != p)
                        {
                           TempRow.push_back(Matrix[i][j]);//add current cell to TempRow 
                        }
                    }
                    if (TempRow.size() > 0)
                        TempMatrix.push_back(TempRow);
                    //after adding each row of the new matrix to the vector tempx
                    //we add it to the vector temp which is the vector where the new 
                    //matrix will be formed
                }
                det = det + Matrix[0][p] * pow(-1, p) * CalcDeterminant(TempMatrix);
                //then we calculate the value of determinant by using a recursive way
                //where we re-call the function by passing to it the new formed matrix
                //we keep doing this until we get our determinant
            }
            return det;
        }
    }
};
\$\endgroup\$
  • \$\begingroup\$ This would be a useful answer on Stack Overflow, although it's not as efficient or numerically robust as other approaches. However, this is the Code Review stack: answers should review OP's code, not just provide a complete reimplementation. \$\endgroup\$ – Peter Taylor Jul 31 '18 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.