Ancient CS 61 Content Warning!!!!!1!!!
This is not the current version of the class.
This site was automatically translated from a wiki. The translation may have introduced mistakes (and the content might have been wrong to begin with).

Matrix multiplication

The cs61-exercises/storage1x directory contains a program called matrixmultiply (source in matrixmultiply.c). This program creates two random square matrices, multiplies them together, prints some information about their product, then exits.

Your job is to transform the fast_matrix_multiply function so that it runs as fast as possible, while producing almost exactly the same results as the original base_matrix_multiply for all arguments.

Matrix multiplication background

A matrix is a 2D array of numbers. An mxn matrix has m rows and n columns; the value in row i and column j is written mij, or, in more C-like notation, m[ij] or m[i][j].

A square matrix has the same number of rows and columns: m = n.

The product of two matrices a and b, written a×b or a*b, is calculated by the following rules.

Some pictures might help. Here’s how the dimensions work:

File:Matmult002.png

And here’s the values used to compute element cij of the destination matrix:

File:Matmult003.png

Matrixes in most languages are stored in row-major order. That means that we store the matrix in a single array, where the values for each row are grouped together. For instance, if a were a 4x4 square matrix, we’d store its elements in this order:

| a[0,0] | a[0,1] | a[0,2] | a[0,3] | a[1,0] | a[1,1] | a[1,2] | a[1,3] | a[2,0] | a[2,1] | a[2,2] | a[2,3] | a[3,0] | a[3,1] | a[3,2] | a[3,3] |

Thus, element aij is stored in array index a[i\*NCOLS + j], where NCOLS is the number of columns (here, 4).

Code

Advanced work

Once you get the “aha” insight you should be able to make fast_matrix_multiply take no more than 0.1x the time of base_matrix_multiply, while producing statistics that are 0% off.

We will crown a winner.

If you have more time to work, complete the following.

Survey

Please fill out the survey!

Solution video