# Matrix multiplication help

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 12-05-2007
Fredir
Matrix multiplication help
I have to do a program to multiply two matrices using 1d arrays, but I am not sure how to begin. What would I need to get from the user--the number of rows in the first array and cols in the second or just how many elements he/she will be inputting?

Also, say the user decides to use 3 rows for array for matrix 1, would I need to create 3 arrays to get the input?

any suggestions are appreciated. Thank you.
• 12-05-2007
dwks
Quote:

What would I need to get from the user--the number of rows in the first array and cols in the second or just how many elements he/she will be inputting?
Probably the rows and columns, because from that information you can determine the total number of elements (rows*cols), but from the total you can't determine the number of rows and cols. (Assuming I've understood you correctly.)

Quote:

Also, say the user decides to use 3 rows for array for matrix 1, would I need to create 3 arrays to get the input?
It sounds like you might want to use dynamic memory allocation. You can use something like this to dynamically allocate a 2D array.
Code:

```int rows, cols; std::cin >> rows >> cols; int **data = new int * [rows]; for(int x = 0; x < rows; x ++) {     data[x] = new int [cols]; }```
• 12-05-2007
Fredir
would this work with a 1 d array as well?
• 12-05-2007
dwks
Umm, sure. 1D arrays are simple.
Code:

```int *array = new int[size]; // ... use array ... delete [] array;```
But I'm going to guess that you don't want 1D arrays. Matricies are 2D, are they not?
• 12-05-2007
tabstop
If you assume the matrix multiplication is valid (which is definitely an assumption), then you have three dimensions: the left is i x j, and the right is j x k. The result will be i x k. So you would need to get those three numbers, and i x j numbers for the first matrix, and j x k numbers for the second, and compute i x k answers for the result.

You can represent these as 1D arrays if you have to (representing A[2][3] as A[2*j+3], etc.), but I would hope you don't have to.
• 12-05-2007
Fredir
I have to use 1d arrays. I still don't get how it would behave like as the 2 d array above, though--can anyone explain?

In other words, how would I input data row by row using this index (A[2*j+3] ) in a for loop?

- also, in that case, I would be asking the user for the number of columns (j), right?

Thank you.
• 12-05-2007
Fredir
dwks, just a minor question, i would have to declare int array to be of a specific size before doing that right?
• 12-05-2007
tabstop
If you have to use 1d arrays, you're going to have to flatten your grid out somehow. For instance, let's look at a 3x3 thing:
a[0][0] a[0][1] a[0][2]
a[1][0] a[1][1] a[1][2]
a[2][0] a[2][1] a[2][2]
There are nine entries, so if we do this we need to use a[0] through a[8]. The question is, are you going to fill in your list: across, or down? Once you do that, then you know how to get from the two-dimensional version to the one-dimensional version.

If you don't know i, j, and k at compile time, well, that just makes the question more interesting.
• 12-05-2007
Fredir
I have to input it across--how would I implement the index in this case? I having a hard time visualizing how to set up the indexes...
• 12-05-2007
VirtualAce
offset = row * width + column;

row = offset / width;
column = offset &#37; width;

For row major matrices (I think).
• 12-05-2007
Fredir
I am not sure how the whole col/row thing is being played out in an array, though. I would appreciate if anyone could explain...thanks.
• 12-05-2007
dwks
Quote:

dwks, just a minor question, i would have to declare int array to be of a specific size before doing that right?
No, you don't. That's the beauty of dynamically allocated data structures (like arrays). You can make them any size, and that size can be determined at run-time.

Here's an example. If I declare an array like so
Code:

`int number[100];`
and read numbers into this array, the user can only enter 100 numbers, and then my program will crash (or at least give an error message if I've written it well). But if I say, "how many numbers do you want?", I can allocate that many numbers, and the user can enter that many numbers.
Code:

```cout << "How many numbers? "; int numbers; cin >> numbers; int *number = new int[numbers]; // ... delete [] number;  // quite important```
There's a third approach, of course: read in numbers until your array is full, and then resize the array if and when you run out of space. That way the user can change the number of numbers that they want at any time. It's a little more complicated to code in C++, however (unlike C . . .), so I'll leave it out for now.

As for that "quite important" comment? One caveat (and benefit) of dynamically allocated memory is that you need to free it. You have to tell the compiler when you're done using the memory. Use delete for memory allocated with new, and delete[] for memory allocated with new[]. (Basically, whether you allocated an array or just a single object.)

So, how can you flatten a 2D array into a 1D array?

First, let's consider how 2D arrays work. When you declare a 2D array of dimensions [X][Y], you get X*Y elements. (Each element might take up 4 bytes, for a int under most platforms, say -- or one byte, for chars, or hundreds of bytes, for more complex elements like classes.) So you get X*Y*sizeof(array[0][0]) bytes of memory.

Now, when you access array[0][0], you're accessing the first element in the array. array[0][1] is the second (if it exists, of course). And so on, until you access array[0][Y-1], the Y-th element. But what is element number Y+1? It's array[1][0]. And then array[1][1] and so on, until you get to the X*Y-th element, the last element, which is array[X-1][Y-1].

Are you familiar with the pointer-like syntax for accessing elements in an array? It goes like this. array[0][0] is the same as **array. array[1][2] is the same as *(*(array + 1) + 2). Right. Of course.

To elaborate: *(*array + 1) is just one element beyond *array, which is the same as array[0]: that is to say, array[0][1]. If you wanted [1][2], you'd take array[0] and add one to get *array + 1, and dereference that to get array[1][0], and add 2 to get array[1][2]. In short, *(*(array + 1) + 2). If this point needs more clarification, let me know.

Now, you can actually do all of this stuff with a 1D array. How? Well, if you declare a 1D array of X*Y elements, you're taking up the same amount of memory as a 2D array of X by Y. You just have to change how you index it. For the first values between (0,0) and (0,Y-1), it's simple. You access 1Darray[0] through 1Darray[Y-1]. Then what? For (1,0) you use 1Darray[Y], and for (1,1) you use 1Darray[Y+1], and so on.

But it turns out that there's an easier way to represent this. Make every pair have a unique index -- a sequential index, so you don't waste any memory. Simple. *(1Darray + x * Y + y). Lost yet? array[1][2] would be 1Darray[1 * Y + 2] in this scheme. It really works. It's sort of like a different base, if you are familiar with numerical bases. Once your Y index reaches its max, you wrap it around to zero and increment the X index. Every X index is equal to Y Y-indicies.

Anyhow, that should give you enough information to figure it out. If not, ask away.
• 12-05-2007
Fredir
thank you so much for the elaborate post. I will see how it goes from here.
dwks, can you give me a brief example of how to declare such an array? I am assuming we need Y (the number of columns) from the user, correct?
-- I am not sure what the y in *(1Darray + x * Y + y) got introduced.
• 12-05-2007
VirtualAce
It's either this:

row * width + column

or

column * width + row

depending on how your array is arranged.
• 12-05-2007
King Mir
Since your doing this in C++, you should probably wrap you matrix in an object. Then overload operator [] to return a pointer to the correct row.

Something like this:
Code:

```class Matrix{     int *m_buffer;     int m_rows, m_cols;     public:     Matrix(int rows, int cols):m_rows(rows),m_cols(cols){         m_buffer=new int[row*col];     };     int *operator [] (int row){         return m_buffer+row*m_cols;     }     ... }```
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last