Multyplying one dimensional dynamic arrays(matrix)

[Cosa]

I am having trouble devising a method to multiply 2 matricies that are formed by dynamic one dimensional arrays, for this case i just used matrix1 and matrix2
To access elements that are on rows 0 to n-1 in either matrix i have to use this method:

((rows - 1) x number of columns) + column number element is on - 1.

I have tried to implement this in a for loop, but i cant get the first row in matrix1 to multiply with the first columnof matrix2. I am having trouble grasping how i would code this for dynamic one dimensional arrays.

[VernonDozier]

I am having trouble devising a method to multiply 2 matricies that are formed by dynamic one dimensional arrays, for this case i just used matrix1 and matrix2 To access elements that are on rows 0 to n-1 in either matrix i have to use this method:

((rows - 1) x number of columns) + column number element is on - 1.

I have tried to implement this in a for loop, but i cant get the first row in matrix1 to multiply with the first columnof matrix2. I am having trouble grasping how i would code this for dynamic one dimensional arrays.

By "multiply", do you mean "multiply" from a linear algebra sense? If so, if you multiply an a x n matrix (a rows, n columns) by an n x b matrix (n rows, b columns) , you end with an a x b matrix result (a rows, b columns).

I assume you mean by "array" a one-dimensional array and by "matrix" you mean a two-dimensional array, though technically you can have a matrix with 1 row or 1 column, which is the equivalent of an array. I don't see, mathematically, why it would matter whether the arrays are dynamically sized or static. The principal would seem to be the same to me, as would the method. You'd probably have to code it slightly differently, but not much. You'd almost certainly have a nested for loop. Anyway, post what you have for the static matrix size case, along with possibly an example of what you're going for in the matrix multiplication.

[hammerhead]

Number of colums in the first matrix have to be equal to the number of rows in the second one. If you have only a row or a column matrix i.e. two arrays, their lengths have to be equal in order for the multiplication to take place.

[Cosa]

sorry for late reply. The way this program has to work is used one dimensional arrays to store a matrix of data. The data is read in from a text file, and is in the format

2 3
12 11 15
13 23 34

This is just an example of a file, the first to integers represent the dimensions of the matrix, so in this case 2 rows and 3 columns. The read in function will prompt for 2 seperate files and read in there data into arrays known as matrixa and matrixb. The dimensions are used to dynamically allocated the size of the array, which is done in the form of

float * matrix = new float[rows * columns]

The data from this array is then copied into matrixa, and then for the next file into matrixb. So my problem is that i have one dimensional arrays, this means the array would look like this after being populated

[12 11 15 13 23 34]

How would i then access elements on the second row? and elements in the columns for multiplication. The method to access these is described to me, however i do not know how to implement it in a loop. The method states "multiply the number of rows minus one * the number of columns on each row, then add the column number minus one to this result. So to access the 2nd element on the second row, it would be sumthing like ((2-1)*3) + (2-1) = 4. So if we count 0..4 we get the second element on the second row which is 23.

I understand the theory behind it, but implementing it in c++ is much more difficult

[dougy83]

Make sure you store the number of rows & cols of each matrix. This may be easier if you put them in a matrix class or struct.

e.g.

struct Matrix{
   float *data;
   int rows, cols;

   float *operator[](int row){
      return &data[row*cols];
      }
   };



Matrix A;
// read maxRows/cols from file
A.data = new float[maxRows * maxCols];
A.rows = maxRows;
A.cols = maxCols;

// now you can reference the data using []
A[2][1] = 5.4;
A[3][3] = 44.9;

[hammerhead]

How would i then access elements on the second row? and elements in the columns for multiplication. The method to access these is described to me, however i do not know how to implement it in a loop. The method states "multiply the number of rows minus one * the number of columns on each row, then add the column number minus one to this result. So to access the 2nd element on the second row, it would be sumthing like ((2-1)*3) + (2-1) = 4. So if we count 0..4 we get the second element on the second row which is 23

The formula can be generalized as

index= ((row_num-1)*3) + (col_num-1)

where index is the index in the array
row_num is the row number of the element you want to refer and
col_num is the column number of the element you want to refer.

Suppose you want to refer to 34
row_num=2
col_num=3

you get index as 5

[Cosa]

Cant use classes, not allowed to, however the dimensions are being passed.

As for the index, that actually clears up things a little.

So would it be sumthing like(just in pseudo)

For i = 0, i < row_a, i++
     for i = 0, i < row_b, i++
            index= ((row_num-1)*3) + (col_num-1)
           then do multiplication here?

[VernonDozier]

Cant use classes, not allowed to, however the dimensions are being passed.

As for the index, that actually clears up things a little.

So would it be sumthing like(just in pseudo)

For i = 0, i < row_a, i++
     for i = 0, i < row_b, i++
            index= ((row_num-1)*3) + (col_num-1)
           then do multiplication here?

Don't hard-code 3 in this line:

index= ((row_num-1)*<strong>3</strong>) + (col_num-1)

You'll have some variable representing the number of columns like num_cols. Put that where the 3 is:

index= ((row_num-1)*<strong>num_cols</strong>) + (col_num-1)

You are also using the same letter, (i) in both loops. You want them to be different. The i++ command in your inner loop will screw up your inner loop count because you are changing i's value. Pick a different loop control variable for the inner loop, like j.

Not exactly sure what you are doing here, but you are not using your loop control variables (i and i, which again should be i and j). You could also row_num and col_num as loop control variables instead of i and j. That might not be a bad idea since those names are more descriptive than i and j.

[Cosa]

That wasnt actual code, just some pseudo, i know that using i in both wouldnt be good. I cant use rows and cols instead becuase they are the count for the amount of time it loops.

Something like this(below) will do it for a multidimensional array. Where would i be able to fit in the index part into this? Possibly use the same style, but for my onedimnesional matrices?

for (i=1; i<=rows_a; i++)
   for (j=1; j<=cols_a; j++)
     {
     sum = 0;
     for (k=1; k<=cols_b; k++)
       sum = sum + matrixa[i][k]*matrixb[k][j];
     }

Once again this isnt actuale code, just pseudo, im just trying to understand the problem, not lookin for actual code.

[VernonDozier]

That wasnt actual code, just some pseudo, i know that using i in both wouldnt be good. I cant use rows and cols instead becuase they are the count for the amount of time it loops.

Something like this(below) will do it for a multidimensional array. Where would i be able to fit in the index part into this?

for (i=1; i<=rows_a; i++)
   for (j=1; j<=cols_a; j++)
     {
     sum = 0;
     for (k=1; k<=cols_b; k++)
       sum = sum + matrixa[i][k]*matrixb[k][j];
     }

Once again this isnt actuale code, just pseudo, im just trying to understand the problem, not lookin for actual code.

Well, looks like you aren't using the 0 index for your arrays, so keep that in mind. Array indexes start at 0, not 1. Maybe change the line from this:

sum = sum + matrixa[i][k]*matrixb[k][j];

to this:

sum = sum + matrixa[i * rows + k] * matrixb[k * rows + j];

I'm guessing that's what you are looking for in turning a 2-D array into 1-D array. You would have to change your earlier declaration from this:

float * matrix = new float[rows * columns]

to this:

float * matrix = new float[(rows + 1) * (columns + 1)];

since you aren't using the 0 index. Otherwise you could get a segmentation fault when i = rows in your loop.

[Cosa]

I have to use rows * columns, thats why when using the index i am told to subtract 1 from the index, sorry if i did not mention that earlier.

So you suggest something like this?

for (j=1; j<=cols_a; j++)
     {
     sum = 0;
     for (k=1; k<=cols_b; k++)
           sum = sum + matrixa[i * rows_b + k] * matrixb[k * rows_a + j];
     }

Im still getting confused as to how exactly these loops work, but it does make a bit more sense, ill have to try and implement this and hopefully it might work.

[VernonDozier]

I have to use rows * columns, thats why when using the index i am told to subtract 1 from the index, sorry if i did not mention that earlier.

You mentioned it. My point is that if you don't use the 0 indices, you have to add 1 when you allocate your array, like this:

float * matrix = new float[(rows + 1) * (columns + 1)];

You'll get a segmentation fault probably if you do this, given the way your loops were set up earlier:

float * matrix = new float[rows * columns];

The way I'm seeing it is that if you have a 2 x 3 matrix:

1 2 3
4 5 6

it'll actually be this since you aren't using the 0 indices:

0 0 0 0
0 1 2 3
0 4 5 6

If you actually are using the 0 indices, you'll have a slightly different offset. Match however you are designing the matrix to how you calculate the offsets. It's not completely clear to me which you are trying to use. It may be the first one, in which case this:

float * matrix = new float[rows * columns];

would work fine, but you would have to be careful to remember to subtract 1 inside your loops.So you suggest something like this?

for (j=1; j<=cols_a; j++)
     {
     sum = 0;
     for (k=1; k<=cols_b; k++)
           sum = sum + matrixa[i * rows_b + k] * matrixb[k * rows_a + j];
     }

Im still getting confused as to how exactly these loops work, but it does make a bit more sense, ill have to try and implement this and hopefully it might work.

Assume the first matrix is called matrixa and the second matrix is called matrixb. matrixa has rows_a number of rows and cols_a number of columns, matrixb has rows_b number of rows and cols_b number of columns. Keep in mind that cols_a and rows_b must be equal. Call the resulting matrix matrix_c. It has rows_c rows and cols_c columns. rows_c will equal rows_a and cols_c will equal cols_b. So to get the 2nd row, 3rd column of matrix_c, you'll do something like this:

float sum = 0;
for (k = 1; k <= cols_a; k++)
{
     sum = sum + matrixa[2 * cols_a + k] * matrixb[k * cols_b + 3];
}
matrixc[2 * cols_c + 3] = sum;

So that's just one element of the multiplied matrix, with the 2 and 3 hard-coded in. You'll want to replace 2 and 3 with other loop control variables, like i and j. So you are going to have nested loops:

for (int i = 1; i <= ?; i++)
{
     for (int j = 1; j <= ?; j++)
     {
          // code very similar to the code above
     }
}

Again, this is assuming you aren't using the 0 indices. If you are, adjust accordingly.

[Cosa]

I see, that makes much more sense, thanx for the help. Ill try to do something like this, and ill report back, thanx again.

[Cosa]

float sum = 0;
	for (int i = 0; i <= rowsa; i++)
	{
		for (int j = 0; j <= columnsa; j++)
		{
			for (int k = 0; k <= columnsb; k++)
			{
				sum = sum + matrixa[i * columnsa + k] * matrixb[k * columnsb + j];
				matrixc[i * columnsb + k] = sum;
			}
			
		}
	}

This is what i have done, the sntax is correct, however the results im getting are wrong. Once again im not to sure if the placement of my values are correct.

[VernonDozier]

float sum = 0;
	for (int i = 0; i <= rowsa; i++)
	{
		for (int j = 0; j <= columnsa; j++)
		{
			for (int k = 0; k <= columnsb; k++)
			{
				sum = sum + matrixa[i * columnsa + k] * matrixb[k * columnsb + j];
				matrixc[i * columnsb + k] = sum;
			}
			
		}
	}

This is what i have done, the sntax is correct, however the results im getting are wrong. Once again im not to sure if the placement of my values are correct.

Please post the program lines where you are declaring the three arrays and filling in values too. If it's not too long, please post the whole program, as that'll put things into context better.

Two things. One, I still can't tell whether you are using the 0 index or not. The fact that you are starting the loops at 0 suggests that you are. The fact that you are using the <= sign rather than the < sign suggests that you are not. It appears to me that you will be going through these loops one too many times potentially. Seeing your entire program will help straighten that out. Two, I think you need to be reinitializing sum to equal 0 every time you you do the multiplication for a new cell. You're only doing it once here, before the top loop. I think you want to initialize sum to equal 0 INSIDE the i and j loops, but BEFORE the k loop starts.

[Cosa]

The program is pretty large, i can post it if you like. I will try use the < insteand of <= and put the sum inside = the loops.

I have done testing on the filled arrays, they get filled properly and are passed to the function, i am delcaring the third matrix in that function, since i do not need it anywhere else, and the ouput will be done within that function.

[Cosa]

if (columnsa != rowsb)
	{
		cout << "cannot multiply matrices!" <<endl;
		return 0;

	}

	float* matrixc = new float[rowsa * columnsb];
	
	for (int i = 0; i < rowsa; i++)
	{
		for (int j = 0; j < columnsa; j++)
		{
			for (int k = 0; k < columnsb; k++)
			{
				float sum = 0;
				sum = sum + matrixa[i * columnsa + k] * matrixb[k * ((rowsb-1) * columnsb) + j];
				matrixc[i * columnsb + k] = sum;
			}
			
		}
	}

This is what i have in the function, it once again produced wrong output. I do feel that it is almost correct, probly just the placing of certain variables

[VernonDozier]

if (columnsa != rowsb)
	{
		cout << "cannot multiply matrices!" <<endl;
		return 0;

	}

	float* matrixc = new float[rowsa * columnsb];
	
	for (int i = 0; i < rowsa; i++)
	{
		for (int j = 0; j < columnsa; j++)
		{
			for (int k = 0; k < columnsb; k++)
			{
				float sum = 0;
				sum = sum + matrixa[i * columnsa + k] * matrixb[k * ((rowsb-1) * columnsb) + j];
				matrixc[i * columnsb + k] = sum;
			}
			
		}
	}

Be very careful about your loop control variables in your three loops. Figure out the dimensions of each of the three arrays and how many times each loop has to be gone through ahead of time and work it out on paper and make sure they match your variables ros_a, columns_b, etc. I'd suggest getting it to work on square matrices first. That way rows_a, rows_b, rows_c, columns_a, columns_b, columns_c are all equal and you can't have any mistakes deriving from when they are different. Get it to work on square matrices first, then move on to where they are not square. If it works for square matrices, but not for the others, then you almost certainly have a problem in the number of times you are going through the loops. Have matrixb be the identity matrix so the math is very easy to check:

1 0 0
0 1 0
0 0 1

The result should be that matrixa is the same as matrixc. That should be your first test case. Also make sure that the arrays are getting to this point accurately. You have a Display function, right? Before multiplying, matrixa and matrixb are correct? I'm guesssing that the problem is confusion among rowsa, rowsb, rowsc, columnsa, columnsb, columnsc, and that at least one is being incorrectly swapped for another. Using square matrices will determine quickly whether that indeed is the problem.

[Cosa]

for (int i = 0; i < (rowsa * columnsa); i++)
	{
		for (int j = 0; j < columnsb; j++)
		{
			for (int k = 1; k < rowsb; k++)
			{
				float sum = 0;
				sum = sum + matrixa[i] * matrixb[((k-1) * columnsb) +(j-1)];
				matrixc[rowsa * columnsb] = sum;
			}
			
		}
	}

I have tried this, but once again its wrong. The problem is that i cant access the correct position in matrixb for the multiplication. Since the matrix is stored in a 1D array, i would either need to add another loop, or change the j loop to start at 1. This then will throw out the rest of the loop.

[VernonDozier]

for (int i = 0; i < (rowsa * columnsa); i++)
	{
		for (int j = 0; j < columnsb; j++)
		{
			for (int k = 1; k < rowsb; k++)
			{
				float sum = 0;
				sum = sum + matrixa[i] * matrixb[((k-1) * columnsb) +(j-1)];
				matrixc[rowsa * columnsb] = sum;
			}
			
		}
	}

I have tried this, but once again its wrong. The problem is that i cant access the correct position in matrixb for the multiplication. Since the matrix is stored in a 1D array, i would either need to add another loop, or change the j loop to start at 1. This then will throw out the rest of the loop.

Change it back to the way you had it before. This line is off:

for (int i = 0; i < (rowsa * columnsa); i++)

Change this line to how you had it before too:

sum = sum + matrixa[i] * matrixb[((k-1) * columnsb) +(j-1)];

Get some square matrices, hard code in the values of rowsa, rowsb, etc., and go back to how you had it before. I think you are going to have to post the rest of your program, trimmed down enough to be complete but still showing everything relevant. If you use square matrices and declared and loaded them correctly, it should have worked before, I think. These revisions are making it worse. But to figure out where you are going wrong, we'll need to see the whole program. How long is it?