# Algorithm to multiply two matrices

#include <iostream>
#include <vector>

void function(std::vector<std::vector<int>>& matrix1, const std::vector<std::vector<int>>& matrix2)
{
std::vector<std::vector<int>> matrix(matrix1.size(), std::vector<int>(matrix1.size()));
int result = 0;
int column = 0;
if (matrix1.size() == matrix2.at(0).size() && matrix1.at(0).size() == matrix2.size())
{
for (int i = 0; i < matrix1.size(); ++i)
{
for (int j = 0; j < matrix1.at(0).size(); ++j)
{
result += matrix1.at(i).at(j) * matrix2.at(j).at(column);
}
matrix.at(i).at(column) = result;
if (column != matrix1.size() - 1)
{
--i;
++column;
}
else
column = 0;
result = 0;
}
}
matrix1 = matrix;
}
int main()
{
std::vector<std::vector<int>> matrix1{ {1,0,2}, {-1,3,1} };
std::vector<std::vector<int>> matrix2{ {3,1}, {2,1}, {1,0} };
function(matrix2, matrix1);
}


The function (i.e. function) multiplies two matrix variables and changes the first parameter(i.e. matrix1). Is it possible to improve my algorithm?

I know that I can change variable names, but that isn't important. Its only an example. Maybe I can avoid two variable ints? I think that I always must create helper variables (matrix).

• Op clearly states that it's example code. – Emily L. Jul 14 '17 at 19:55
• @EmilyL. Re: "Op clearly states that it's example code." -> not clear to me at all. I think this should stay open. – janos Jul 15 '17 at 12:59
• Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. – Simon Forsberg Jul 16 '17 at 10:32

1. Well, first you should create your own class for matrices. Your current ad-hoc representation is inefficient and lacks abstraction.
Options include:

• Row-major or column-major.
• Restricted to specific dimensions / square matrices.
• Using an array of pointers to rows/colums or explicit mapping of coordinates to ids.
2. Is there a reason you insist that the result-matrix should be square? Seems gratuitious.

3. There's no advantage to modifying the first input instead of returning a new matrix. So, make both arguments constant and return the result instead.

4. If you don't need an object any longer after copying it, might moving be more appropriate, as it's potentially more efficient and less likely to throw?

• 1. It is example. This algorithm is in class which taken only one matrix. 3. Algorithm modify this in my class so example is simply. 2. Yes, you have right, it's mistake. – 21koizyd Jul 14 '17 at 17:17
• 2. improve. 4. improve. – 21koizyd Jul 14 '17 at 17:23

Matrix multiplication, while it seems trivial to implement from the definition, the naive implementation you are using is actually slow for anything but small matrices.

You really should look into more efficient algorithms for matrix multiplication, a good place to start is the Wikipedia page here: Matrix multiplication algorithm.

A matrix multiplication algorithm usually involves three for loops. The fact that you are using two for loops and use some obtuse logic to reset indices point to unclear thinking on your part. As a matter of fact, there is an error in your logic and is easily exposed if you allow for multiplication of matrices that don't result in square matrices.

If you change

if (matrix1.size() == matrix2.at(0).size() && matrix1.at(0).size() == matrix2.size())


to

if (matrix1.at(0).size() == matrix2.size())


you allow multiplication of matrices that don't result in a square matrix. However, if you multiply the following matrices with just that change,

std::vector<std::vector<int>> matrix1{ { 1,0,2,1 },{ -1,3,1,2 } };
std::vector<std::vector<int>> matrix2{ { 3,1 },{ 2,1 },{ 1,0 } };
function(matrix2, matrix1);


you will notice that the resultant is not correct. It ends up being

2 3 7 0
1 3 5 0
1 0 2 0


Please note that the correct one needs to be:

2 3 7 5
1 3 5 4
1 0 2 1


By changing the function to

void function(std::vector<std::vector<int>>& matrix1,
const std::vector<std::vector<int>>& matrix2)
{
std::vector<std::vector<int>> matrix(matrix1.size(), std::vector<int>(matrix2.at(0).size()));
if (matrix1.at(0).size() == matrix2.size())
{
for (size_t i = 0; i < matrix1.size(); ++i)
{
for (size_t j = 0; j < matrix1.at(0).size(); ++j)
{
for (size_t k = 0; k < matrix2.at(0).size(); ++k )
{
matrix.at(i).at(k) += matrix1.at(i).at(j) * matrix2.at(j).at(k);
}
}
}
}
else
throw std::invalid_argument("Invalid syntax");
matrix1 = std::move(matrix);
}


that error is fixed.

Please note that I changed the type of i and j to size_t from int.