Waffle Matrices…Mmmm Where is the Syrup?

Have you ever sat at the kitchen table where you mom made you a big stack of waffles only to stare at the squares and realize it could be a matrix? Young child programmers do all the time! Heck you might have even written in random numbers using syrup into each square before eating it all up. Skyhawk133 wanted me to make a video on this very subject and while a video is a waste of time on a subject like this, a blog entry sure isn’t! Lets get down with some waffle math! We will disect our waffles using C++ and figure out how to do some multiplication of matrices…. on this entry of the Programmer’s Underground!

Mathematicians use matrices for all sorts of things and programmers can use it for changing colors in bitmap images as well as other projects. I decided to dive into the theory using a good wholesome breakfast treat, waffles. No waffle math is not an official sport yet, but we here at DIC plan on submitting it for consideration in the next Olympic games. Along with the waffle toss, waffle chase, and a good game of Waffleshoes… its like horseshoe, but with waffles. Just wait and see.

But anyways, a matrix can be thought of as a 2 dimensional array, or grid like structure which contains numbers. They can be virtually any size, but two matrices that are to be multiplied should have the number of columns in the first to match the number of rows in the other. For instance, a waffle of 3 X 4 should be multiplied against another waffle only if its rows match 4, the number of columns in the first waffle. To simplify matters, we will multiply two matrices of the same size… 4 x 4. Lets take a look!

X =

So how do we multiply waffle A against waffle B to get waffle C? The process is pretty straight forward but takes a bit of time by hand.

We start by taking row 1 of waffle A and multiply it by column 1 of waffle B. We then add them up to get the first number for waffle C. So we go… (3*2) + (7*3) + (4*7) + (6*5) = 85. We then place 85 in waffle cell 0,0. Next we take row 1 of waffle A and multiply it against column 2 of waffle B and add them up again. (3*4) + (7*1) + (4*4) + (6*3) = 53 and we place that number in cell 0,1 of waffle C. We continue like that until we run out of numbers for row 1. We then start with row 2 of waffle A and column 1 of waffle B and continue. We move through each of the columns for a given row of waffle A until we run out of rows and columns. Leaving us with a waffle C with the dimensions of (rows in waffle ‘A’ x columns in waffle ‘B’).

Hopefully that wasn’t too confusing. So in C++ we must make sure our resulting matrix has the dimensions of rows from matrix 1 and columns of matrix 2. Lets take a look at how that could be done…

```#include <iostream>
#include <stdlib.h>
#include <ctime>
using namespace std;

// Declarations for our three functions.
void printResults(int **, int, int);
void fillArray(int **,int, int);
void multiplyWaffles(int **, int **, int **, int, int, int);

int main() {
// Collect Waffle information
int rowA = 0, colA = 0, rowB = 0, colB = 0;
cout << "How many rows to Waffle 'A': ";
cin >> rowA;

cout << "How many columns to Waffle 'A': ";
cin >> colA;

cout << "How many columns to Waffle 'B': ";
cin >> colB;

// To multiply, rows in B must be same as columns in A.
rowB = colA;

// Seed our random number generator using system time.
srand((int)time(NULL));

// Setup Waffle A, fill it with int pointers of specified dimensions.
int **WaffleA;

WaffleA = new int*[rowA];

for (int i = 0; i < rowA; i++) {
WaffleA[i] = new int[colA];
}

// Fill it with random numbers
fillArray(WaffleA,rowA,colA);

// Print out the contents of the matrix (Waffle)
cout << "Waffle A..." << endl;
printResults(WaffleA,rowA,colA);

// Setup Waffle B, fill it with int pointers and random numbers
// Just like we did for Waffle A
int **WaffleB;

WaffleB = new int*[rowB];
for (int i = 0; i < rowB; i++) {
WaffleB[i] = new int[colB];
}

fillArray(WaffleB,rowB,colB);
cout << "\nWaffle B..." << endl;
printResults(WaffleB,rowB,colB);

// Again, setup Waffle C just like A and B except use
// Rows from A and columns from B (resulting matrix is rows from 1st and columns from 2nd)
int **WaffleC;

WaffleC = new int*[rowA];
for (int i = 0; i < rowA; i++) {
WaffleC[i] = new int[colB];
}

// Multiply them together, passing all waffles, the rows from A, Columns from A
// (could use rows from B since they are the same) and column from B
multiplyWaffles(WaffleA,WaffleB,WaffleC,rowA,colA,colB);

// Print the resulting Waffle which is our multiplied matrix.
cout << "\nWaffle C..." << endl;
printResults(WaffleC,rowA,colB);

// Cleanup our waffles.
delete(WaffleA);
delete(WaffleB);
delete(WaffleC);

return 0;
}

// Prints a given waffle passed in by pointer.
void printResults(int **results, int rows, int cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cout << "Row & col: " << i << " / " << j << " - " << results[i][j] << endl;
}
}
}

// Fill the given array (passed by pointers to an array of pointers... 2D array)
void fillArray(int **arFill, int rows, int cols) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
arFill[i][j] = rand() % 10;
}
}
}

// Multiplies the rows from A against the columns of B and sums them up in rows/columns of Waffle C
// Again all three Waffles passed in by 2D array of pointers.
void multiplyWaffles(int **WaffleA, int **WaffleB, int **WaffleC, int rowA, int colA, int colB) {
for (int i = 0; i < rowA; i++) {
for (int j = 0; j < colB; j++) {
WaffleC[i][j] = 0;
// Once we have the row and the column, we need the indexer to move
// down the column and sum them up into WaffleC result matrix.
for (int k = 0; k < colA; k++) {
WaffleC[i][j] += (WaffleA[i][k] * WaffleB[k][j]);
}
}
}
}
```

In the code above we establish three 2D arrays… matrices. I named them Waffle A, B and C. I first ask the user for the rows and columns of the first matrix and only the column of the second matrix since we already know that waffleB’s rows will have to match the columns of waffleA. After collecting those integers, we first call fillArray to fill up our waffles with random numbers. I generated the numbers using srand()… a function found in stdlib.h. I pass both waffle A and waffle B to this function for filling and then I output the results using the printResults() function. So you can see what numbers went in each waffle.

Now we have two waffles, A and B, which are full of random numbers. We pass pointers to them to our multiplyWaffles() function which will do the multiplication. This function takes quite a few parameters. Pointers to both waffle A and waffle B as well as the result waffle C. It takes the row count from waffle A as well as the column count (this number could have been the row count from waffle B since they are the same number) and lastly the column count from waffle B.

We construct three for loop statements. One moves through the rows of waffle A, while the other moves through the columns of waffle B, and the innermost loop loops through the numbers in that column to create a sum (which we then store in waffle C at the row and column coordinates). We could have created an accumulator variable to hold the values of the sum and then dump it into the right waffle space on waffle C, but this was a bit of a shortcut to save us from defining an extra variable.

The process is pretty simple if you are familiar with moving through a 2D array. We are essentially moving through a row, accessing the column and then all values in that column to come up with the sum. The result of this process is waffle C which is shown above.

So there it is, multiplication by waffles. Breakfast time will never be the same! Feel free to use the code above for whatever you want to do with it. I can’t expect to corner the market on waffle math. It is a gift that belongs to humanity, not a single man like myself. Consider it a gift to all you programmers out there in DIC land. On the next episode of Martyr2’s Programming Underground, we cover HTML tables by actually sawing a table in pieces! Should be fun! (jk, don’t send me PMs about when that blog entry will come along).

Thanks for reading and enjoy the waffles! ðŸ™‚