Multiply matrix with itself n times

[WAKS]

Hi!
I'm working on a school assignment where I need to multiply a matrix with itself n times to find the least number of throws needed to finish a snakes and ladder game. The problem is that I'm getting the wrong probability and number of throws, and I think that the problem lies in my matrix multiplication.

//SIZE is the size of the board rows and columns

	for (int i = 1; i <= SIZE; i++)
	{
		for (int n = 1; n <= SIZE; n++)
		{
			result[i][n] = board[i][n];
		}
	}

	int count = 1;
	while (result[1][SIZE] == 0) 
	{	
		for (int i = 1; i <= SIZE; ++i)
		{
			for (int n = 1; n <= SIZE; ++n)
			{
				for (int k = 1; k <= SIZE; ++k)
				{
					result[i][n] += board[i][k] * result[k][n];
					
				}
			}
		}
		count++;
	}
	
	cout << "At least " << count << "throws" << "\n";
	cout << "P(at least " << count << ") " << result[1][SIZE] << "\n";

[Peter87]

Note that indices start at 0 which means the highest valid index is SIZE - 1.

I think another problem is that you are modifying the values in the matrix while calculating the matrix multiplication.

[WAKS]

@Peter87
I know, but I have created my program so every matrix counts from 1-SIZE. Becuase it's easier for me to think on the math when everything counts from 1. I have therefore changed every for loop to go from 1 to <= SIZE instead of 0 to < SIZE

I think another problem is that you are modifying the matrix while calculating the multiplication

That could be the problem, but how could I fix that?

[keskiverto]

Conceptually:

Mat board;
Mat result( board );
while ( cond ) {
  Mat tmp( board * result );
  result = tmp;
}

For the result = tmp; you might be able to use std::move or std::swap as optimization.

[Peter87]

WAKS wrote:

I have created my program so every matrix counts from 1-SIZE. Becuase it's easier for me to think on the math when everything counts from 1. I have therefore changed every for loop to go from 1 to <= SIZE instead of 0 to < SIZE.

I hope you have also allocated the extra space when creating the matrix.

double board[SIZE + 1][SIZE + 1];

WAKS wrote:

That could be the problem, but how could I fix that?

I was going to suggest you should use another matrix to store the result but I see you are already using two different matrices. I think you should read both values that you multiply from the board array (at the moment you read one from board and one from result).

result[i][n] += board[i][k] * board[k][n];

Now if you initialize the result array to zero, and the while loop only runs once (meaning you only want to multiply the matrix with itself once) you will probably get the correct result.

To be able to handle multiple matrix multiplications you would have to make sure that the values of result is copied (or in some other way transferred) to board after each matrix multiplication. You also need to make sure the result array is restored to zero before each matrix multiplication.

To make the code easier to work with you might want to separate the code into functions. First you could create a function that do the matrix multiplication (once). When you have tested and made sure that the function is working correctly you can just call it, from your other code, the number of times you want to multiply.

I don't really understand your while loop condition to be honest. Maybe that's how you want it, but just so that you know, if you are using floating point numbers you should be very careful comparing them using == because floating point values are not always exact and might contain rounding errors.

[jonnin]

This might be worth a read.

http://people.revoledu.com/kardi/tutorial/LinearAlgebra/MatrixPower.html

You can also do a little better by doing
r = A*A,
x = r*r
z = x*x
...

approach, to reduce the # of multiplies. You can pull these back together to get other powers, like z*r*a.

Brute force, as you have it, also works, just kicking around some improvements to think about as you learn.

[lastchance]

As @Keskiverto and @Peter87 have noted, you MUST have temporary store whilst you are doing that matrix multiply - otherwise you are updating parts of the matrix that you are still using in the multiply. You must also initialise the element to zero before you start adding the inner product of a row and column to it.

In common with the earlier replies I would advocate using a separate function to do the matrix multiply - it can then be easily tested. However, to try to stay within your format I have tried to add comments and some minor modifications to your current code. I have no way of testing it, I'm afraid, as it isn't complete code. (Sorry, I've also lost your tabs - they made editing impossible.)

        for (int i = 1; i <= SIZE; i++)
        {
                for (int n = 1; n <= SIZE; n++)
                {
                        result[i][n] = board[i][n];     // result[][] will hold the current power of the matrix board[][]
                }
        }

        int count = 1;

        double temp[1+SIZE][1+SIZE] = { 0 };            // <==== YOU DO NEED TEMPORARY STORAGE (might be float, rather than double)


        while (result[1][SIZE] == 0)                    // repeatedly multiply until there is a non-zero probability of having reached the end square
        {       


                for (int i = 1; i <= SIZE; ++i)         // matrix multiply starts here (i is row, n is column)
                {
                        for (int n = 1; n <= SIZE; ++n)
                        {
                                temp[i][n] = 0;              // <===== MUST INITIALISE THIS ELEMENT TO ZERO
                                for (int k = 1; k <= SIZE; ++k)                             // multiply ith row by nth column
                                {
                                        temp[i][n] += board[i][k] * result[k][n];           // <===== LEFT-HAND SIDE MUST BE TEMPORARY STORE
                                        
                                }
                        }
                }


                for (int i = 1; i <= SIZE; i++)              // <====== 
                {                                            // <======
                        for (int n = 1; n <= SIZE; n++)      // <======
                        {                                    // <====== NOW COPY MATRIX PRODUCT BACK INTO result[][]
                                 result[i][n] = temp[i][n];  // <======    
                        }                                    // <======
                }                                            // <======

                count++;
        }

[WAKS]

First of all, thanks for all the help. You all where right about the temporary matrix.

you MUST have temporary store whilst you are doing that matrix multiply - otherwise you are updating parts of the matrix that you are still using in the multiply.

@lastchance I tried out the changes you did to the code and it works flawlessly. I don't understand why I didn't see the problem before. Because it's is very obvious now when I see the temp matrix in use, that I was updating the result matrix while it still was used in the multiplication.