Matrix multiplication help

This is a discussion on Matrix multiplication help within the C++ Programming forums, part of the General Programming Boards category; I have to do a program to multiply two matrices using 1d arrays, but I am not sure how to ...

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    60

    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.

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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.)

    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];
    }
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    60
    would this work with a 1 d array as well?

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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?
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  6. #6
    Registered User
    Join Date
    Oct 2007
    Posts
    60
    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.
    Last edited by Fredir; 12-05-2007 at 02:22 PM.

  7. #7
    Registered User
    Join Date
    Oct 2007
    Posts
    60
    dwks, just a minor question, i would have to declare int array to be of a specific size before doing that right?

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  9. #9
    Registered User
    Join Date
    Oct 2007
    Posts
    60
    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...

  10. #10
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    offset = row * width + column;

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


    For row major matrices (I think).

  11. #11
    Registered User
    Join Date
    Oct 2007
    Posts
    60
    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. #12
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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.
    Last edited by dwks; 12-05-2007 at 05:26 PM.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  13. #13
    Registered User
    Join Date
    Oct 2007
    Posts
    60
    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.
    Last edited by Fredir; 12-05-2007 at 06:13 PM.

  14. #14
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    It's either this:

    row * width + column

    or

    column * width + row

    depending on how your array is arranged.

  15. #15
    Registered User
    Join Date
    Apr 2006
    Posts
    2,046
    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;
        }
        ...
    }
    Last edited by King Mir; 12-05-2007 at 10:26 PM. Reason: Bin doing too much java recently.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 01:30 PM
  2. *operator overloading: scalar matrix multiplication
    By gemini_shooter in forum C++ Programming
    Replies: 4
    Last Post: 06-08-2009, 01:14 PM
  3. Matrix Multiplication ( Accessing data from a file ) HELP
    By six_degreez in forum C Programming
    Replies: 2
    Last Post: 07-24-2008, 05:21 PM
  4. Matrix Help
    By HelpmeMark in forum C++ Programming
    Replies: 27
    Last Post: 03-06-2008, 04:57 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21