Tag Archives: matrix

Neo Must Die – Give us the Matrix

We don’t want to be free. Neo is our enemy, not our savior.

Most of us have seen The Matrix, or are at least familiar with the story. Neo is our hero in the movie, a virtual god in training, selflessly seeking to destroy the Matrix and free the enslaved humans therein.

Yet, curiously, one of the freed humans desires to get back into the Matrix. “Ignorance is bliss,” proclaims Cypher. Tired of the grit of the real world, he wants to enjoy his virtual steak in a comfortable booth in a nice restaurant in oblivion. Obviously the bad guy, he makes a deal with the Agents and betrays Neo and the crew.

Pointless to ask which character do you identify with more?

The ironic truth is that we humans are willingly inserting ourselves into the Matrix. We don’t need to wait for the Machines to come get us. We’re building them and strapping them on, plugging them in, and embedding ourselves within them.

Think of these trends:

  1. iPods – It seems like there are nearly as many pairs of white ear buds as humans. It is easier than ever to block out the deafening silence with music, podcasts, and tiny videos for the attention-challenged masses. Do I have an iPod that I listen to while cooking, cleaning, building Legos, driving, falling asleep? You betcha.
  2. World of Warcraft, Second Life, other MMORPGS – I think the resemblance of these to the Matrix is actually more superficial than anything else. They are obvious fantasy playgrounds. And yet…we read about WoW weddings, offline guilds, and more. Companies have virtual presences in Second Life. Real estate is bought and sold. Compare the experience of Mildred in Fahrenheit 451 and her 3-walled interactive-TV enclosure. Is that some way between virtual realities and alternate, livable realities? Does your Second Life avatar look just like you? Why not?
  3. 24-hour news – It’s cliché to rail against the 24-hour media, and I don’t want to do that specifically. But it is another aspect of being “plugged in” to the world. We always have to know what’s going on everywhere (ignoring for the moment that most TV news is now tabloid and worthless).
  4. Facebook, mySpace, etc. – These online communities have replaced many of the traditional face-to-face interactions we partake in. We count our friends, visit their pages, listen to their music, understand and comment on their thoughts, sometimes without ever actually meeting.
  5. Twitter – is there anything more Borg-like than being continually updated with the status of hundreds of other individuals? Once we harness this power we, in effect, become individual cogs in a great machine.
  6. Rise of Video over Literature – Books are still incredibly popular and probably will be forever, but the potential exists for books to be superceded by video-on-demand. We’ve always had a “Matrix” in our minds–a place to escape to, interpreting the words on the page however we like. With video, however, the vision is placed upon us and we become part of it, rather than it becoming part of us.
  7. Simplifying life by placing organization burdens on computers – PDAs, Getting Things Done, Outlook. Unburdening our crowded minds, allowing the computer to track our lives for us, freeing us for more important pursuits. Rather than mindless tasks that we all must do, we can focus our energy on our creativity.

What happens to the human race as our reality is supplemented so heavily by virtual realities, by computers, by constant flows of information, and yet coincidentally we have so many automated processes to filter and store that information for when we need it. Do we become hyper-productive and fantastically creative? Do we enjoy the fruits of nearly infinite resources like learning and exploration for its own sake? Or do we become lazy and unproductive, mere taskmasters over the computers which run our lives, stuck in fantasy worlds more exciting than our own?

It’s not that any of these things are bad. What is evident now is that the Matrix itself isn’t bad. Neo is the Luddite trying to hold us back, pull us out of the hyper-connected, multiplexed virtual realities of the 21st century into the grim shadows of “real” life. Real life–that which deals pain equally with joy, sadness with happiness, tough breaks with outstanding successes, where you’re paid to work, not play, not be a hero.

Of course, the Matrix portrays a world equivalent to our own, with the real world being brutally harsh for human existence. But the difference is only in degree. Either way, we’re happier being in a virtual world that is somehow more attractive than the one we physically exist in.

Neo must die. Leave us alone to enjoy our fantasies, our electronically-fueled dalliances in worlds unknown.

Technorati Tags: , , , , ,


Check out my latest book, the essential, in-depth guide to performance for all .NET developers:

Writing High-Performance.NET Code, 2nd Edition by Ben Watson. Available for pre-order:

Operator Overloading in C++

Definition

This can be a weird subject for some, especially those with a strong Java background, or another language that doesn’t support this feature. It can be confusing even for excellent programmers. But it is a strong feature of C++ that, if mastered, can yield some increased productivity in programming.

We all know that an operator can be used in mathematical expressions:

[code lang=”cpp”]
int z=x+y;
float g=3.14*g;
[/code]

Now wouldn’t it be nice to use operators on our own objects to do what we want? For example, a string class could use + to concatenate, or a Throttle class could use the ++ and — operators to increase or decrease throttle position. The operators can be programmed to do whatever we want them to.

However, some words of caution. Operator overloading provides NO additional functionality to your code. It just compiles to normal function calls. It’s even written out like normal function calls. It is mainly for aesthetics. There is, however, one extremely useful set of operators to overload that makes life much easier: the streaming operators, which I will cover at the end.

Second, you should NOT use operator overloading for unobvious relationships. Using + to concatenate two strings intuitively makes sense to most programmers, so it’s easy to use it like that. But how would you define string1*string2? or string1^string2? It isn’t very clear what that means. So use caution when considering adding operators to your objects.

Sample Object

For my sample object, I’m going to implement a matrix. This won’t be a full-scale implementation of every imaginable matrix operation, but it should be enough to cover the basics of operator overloading, and maybe whet your appetite to complete the implementation for other operations (dot product, inverse, determinant, etc.).

In order to completely encapsulate a matrix within a class, we actually need two classes: Row and Matrix.

So let’s start with Row:
[code lang=”cpp”]
template
class Row {
public:
Row(int cols=0):row(NULL) {SetRowSize(cols);}
~Row() {SetRowSize(0); }
Row(const Row &r):row(NULL) {
SetRowSize(r.numCols);
for (int i=0;i row[i]=r.row[i];
}

void SetRowSize(int n) {
if(row) delete[] row;
if (n>0) {
row=new T[n];
memset(row,0,sizeof(T)*n/sizeof(char));
}
else row=NULL;
numCols=n;
}

int size() { return numCols;}
private:
int numCols;
T* row;
};[/code]

Let’s look at this before continuing on. Notice that I’m making it a template class. This is so you can have a matrix of all the usual numerical types, as well as any type you want to define yourself. The only requirement for the type is that it must have the +, -, and * operators defined on it. We’ll get into how to do that. If you don’t understand templates, you can think of all of the T’s as ints for now.

SetRowSize() deletes any old data, and allocates space for new data, unless we set the number of columns to 0, in which case it merely deletes the data. This lets us use this function for construction, destruction, and dynamic modification in one method. Nifty, eh? The call to memset() just zeroes out the array after figuring out how many bytes the row uses and dividing this by the size of character, because memset() works in terms of chars.

I also defined a copy constructor, which will come in handy quite a bit, as we’ll see later on when we copy matrices.

Overloading []

OK, let’s overload our first operator: []

Yes, that’s one operator. The array-access operator. It makes perfect sense here, because we have a linear array of objects we would like to access. Let’s add this definition to our Row class:
[code lang=”cpp”]
T& operator[](int column) {
assert(column return row[column];
}
[/code]

The arguments to our brackets are going to be integers specifying the index of the item we want, so that will be the function’s arguments. Notice the syntax: [ReturnType] operator[Op]([argument list]). We do an assertion to make sure we’re accessing memory within the array’s bounds. If all is OK, we return a reference to the object. Why a reference instead of a value? It won’t make much of a difference in a case like this:

[code]
Row r(1);//1×1 matrix

int a=r[0];
[/code]

a will get the value of r[0] whether a reference or a value is returned. However, if we return a reference, we can then change the value in the row from outside the class, using the [] accessor operator, like so:
[code lang=”cpp”]
Row r(1);

r[0]=3.142;
float pi=r[0];
[/code]

Very cool, isn’t it.

Overloading =

The only other operator we need to overload is assignment (=). When overloading assignment, we must keep in mind that the object we’re assigning to must already exist, and it is that object’s operator= method which will be called.
[code lang=”cpp”]
Row& operator=(const Row& r) {
SetRowSize(r.numCols);
for (int i=0;i row[i]=r.row[i];
return *this;
}
[/code]

Again we return a reference, but this time it’s a reference to itself. First we set the size of the current row equal to that of the source row, then we copy its values. There is an important note here. Notice that I’m using [] on the primitive T array itself–NOT the overloaded []s of Row. Remember that Row’s [] returns a reference, thus if we had written row[i]=r[i], we would get a row that references the exact same data in memory, so that when we changed one the other would change–this isn’t what we want at all, so we need to access the raw data in the Row class.

Now we can write code like this:
[code lang=”cpp”]
Row r1(5);
Row r2;//creates an empty row
Row r3(2);
r2=r1;
r3=r1;//overwrites previous row information to contain same info as r1
[/code]

Matrices are Made of Many Rows

Now that we have a working Row, we can combine rows into a matrix. Let’s start with this basic definition:
[code lang=”cpp”]
template
class Matrix {
public:
Matrix(int rows=0, int cols=0): matrix(NULL) {
SetSize(rows,cols);
}
Matrix(const Matrix& m): matrix(NULL) {
SetSize(m.numRows,m.numCols);
for (int r=0;r matrix[r]=Row(m.matrix[r]);//assign to primitive array, NOT overloaded []–to get a copy
}
void SetSize(int rows, int cols) {
if (rows) delete[]matrix;
if (cols > 0 && rows >0) {
matrix=new Row[rows];
for (int i=0;i matrix[i].SetRowSize(cols);
}
else
rows=NULL;
numCols=cols;numRows=rows;
}
int GetCols() { return numCols;}
int GetRows() { return numRows;}

private:
int numCols, numRows;
Row* matrix;

};
[/code]

This follows very closely the basic form of the Row class. The only item of interest is when we declare and allocate a matrix: we must specify the type, T, after the class name.

First let’s implement the same operators we did on the Row class:
[code lang=”cpp”]
Row& operator[](int index) {
assert(index return matrix[index];
}

Matrix& operator=(const Matrix& m) {
SetSize(m.numRows,m.numCols);
for (int r=0;r matrix[r]=Row(m.matrix[r]);//assign to primitive array, NOT overloaded []–to get a copy
return *this;
}
[/code]

The most important part of this code is the return type of operator[]. It returns a reference to a Row of type T. This little fact allows us to use the Matrix class like this:
[code lang=”cpp”]
Matrix a(2,2);

a[0][0]=2;
a[0][1]=4;
a[1][0]=8;
a[1][1]=16;
[/code]

That is, we can refer to Matrix objects now with exactly the same notation as primitive 2-D arrays in C++: array[row][column]. Our operator overloading is faking it well enough to keep a consistent interface with analogous structures, but add much more functionality and safety. Isn’t this cool?

The = operator works the same way as in Row. It sets the size of the current Matrix to that of the source, and then copies all of the objects to the current Matrix. Now we can do the following:
[code lang=”cpp”]
Matrix<__int64> m(1000,1000);
Matrix<__int64> n=m;
[/code]

…and we have two very large matrices of 64-bit integers.

Overloading +

Let’s do some more interesting things with these matrices now. There are a number of mathematical operations that can be performed on a matrix, the simplest perhaps is addition. Addition of matrices requires that they both have the same dimensions. The resulting matrix is made by simply adding each number in the same position in each matrix and putting the answer in the same position as the two operands.
[code lang=”cpp”]
[1 0] [4 3] [5 3]
[2 1] + [-1 0] = [1 1]
[/code]

Since addition creates a new matrix, we don’t want to return a reference, but an actual matrix object. Here’s what the code looks like:
[code lang=”cpp”]
const Matrix operator+( const Matrix& m) {
assert(numCols==m.numCols && numRows==m.numRows);
Matrix theMatrix(numRows,numCols);
for (int r=0;r for (int c=0;c theMatrix[r][c]=matrix[r][c]+m.matrix[r][c];
return theMatrix;
}
[/code]

This adds the current matrix to the matrix in argument m. We first assure that the dimensions are equivalent, then create a new matrix with the same dimensions as the sources. It is then a simple matter of adding the two sources, and returning the new matrix. Notice that we perform the actual math on the types that make up each row.
[code lang=”cpp”]
Matrix a(2,2);
Matrix b(2,2);
Matrix c(2,3);
Matrix d=a+b;
Matrix e=a+c;//will fail assertion, abort program
[/code]

It is just as easy to define subtraction:
[code lang=”cpp”]
const Matrix operator-( const Matrix& m) {
assert(numCols==m.numCols && numRows==m.numRows);
Matrix theMatrix(numRows,numCols);
for (int r=0;r for (int c=0;c theMatrix[r][c]=matrix[r][c]-m.matrix[r][c];
return theMatrix;
}
[/code]

Overloading += and -=

+= and -= are operators that both add and change the current object, so the code to describe it is a combination of +/- and =. We’ll return a reference again because we don’t want to create a new object, but just modify the existing one, which called the function. We’ll just add whatever is currently in it to the other matrix, and return a reference to itself:
[code lang=”cpp”]
Matrix& operator+=(const Matrix& m) {
assert(numCols==m.numCols && numRows==m.numRows);
for (int r=0;r for (int c=0;c matrix[r][c]+=m.matrix[r][c];
return *this;
}

Matrix& operator-=( const Matrix& m) {
assert(numCols==m.numCols && numRows==m.numRows);
for (int r=0;r for (int c=0;c matrix[r][c]-=m.matrix[r][c];
return *this;
}
[/code]

We can now expand our repertoire to include the following possibilities:
[code lang=”cpp”]
Matrix a(2,1);
Matrix b(2,1);

a+=b;
a-=b;
[/code]

Scaling: Overloading *

Another useful operation we can perform on matrices is scaling. This just multiples every element in the matrix by a constant.
[code lang=”cpp”]
[1 2] [2 4]
[2 4] * 2 = [4 8]
[/code]

This operation returns a new matrix so we will return by value, not reference. The code should be trivial to read by now:
[code lang=”cpp”]
const Matrix operator*(const float s) {
Matrix theMatrix(numRows,numCols);
for (int r=0;r for (int c=0;c theMatrix[r][c]=matrix[r][c]*s;
return theMatrix;
}
[/code]

We use a float as the scalar, and multiply it by every value in the source matrix, and return a new matrix. It is left up to the reader to implement *=. (/ and /= could also be implemented as inverses of scaling, but since scaling allows a float, this is mostly redundant.)

Matrix Multiplication – Overloading * again

We can actually overload the same operator more than once if we would like. As long as the function’s signature (return type, name, and arguments) is different, we can define as many as we want. The * operator would be a likely candidate for implementing matrix multiplication as well as scaling. Both imply multiplication of some sort, so it should make sense.

Matrix multiplication has a requirement: the number of columns in the first matrix must be equal to the number of rows in the second. Matrix multiplication is NOT commutative. I won’t explain how to do matrix multiplcation–it’s easy enough to look up this topic on-line or in a math textbook. Or you can deduce the “by-hand” algorithm from the code.
[code lang=”cpp”]
const Matrix operator*(Matrix& m) {
assert(numCols==m.numRows);
Matrix theMatrix(numRows,m.numCols);
for (int r=0;r for (int c=0;c for (int i=0;i theMatrix[r][c]+=matrix[r][i]*m[i][c];
}
}
}
return theMatrix;
}
[/code]

Overloading < < and >>

There are only two more important operators that I will cover here. These are perhaps the operators that should be implemented for each and every class you create. The streaming operators < < and >> allow your object to be saved and restored from any stream, be it console, network, or file.

There is a slight additional challenge with these operators because we must allow the stream access to our object’s private data. Therefore, these functions must be declared as friends inside the Matrix class.

Let’s first look at outputting to a stream:
[code lang=”cpp”]
friend ostream& operator< <(ostream& os,const Matrix& m) {
os << m.numRows<<” “< Matrix a(2,2);

cout < <“Matrix a:”<

ofstream ofile(“output.dat”);
ofile << a << endl<<“End of File”;
[/code]

It is a quite similar technique to read in values from a stream:
[code lang=”cpp”]
friend istream& operator>>(istream& is, Matrix& m) {
int rows,cols;
is >> rows >> cols;
m.SetSize(rows,cols);
for (int r=0;r for (int c=0;c is >> m[r][c];
return is;
}
[/code]

Here we declare some local variables to hold our matrix dimensions, which we then pass to the referenced matrix object. Then it’s just a matter of reading in the next number and putting it in the appropriate location. We then return a reference to the stream in case the calling function wanted to continue getting data from it in the same command.

Putting it all together

To demonstrate the Matrix class and its overloaded operators, I’ve written a sample main() as well as some helper functions that will run the class through its paces:

[code lang=”cpp”]
//the functions fill in a matrix with random values–they are type-specific
void init_matrix(Matrix& m) {
for (int r=0;r for (int c=0;c m[r][c]=rand()%5+1;
}

void init_matrix(Matrix<__int64>& m) {
for (int r=0;r for (int c=0;c m[r][c]=rand()%100000+1;
}

void init_matrix(Matrix& m, int precision) {
for (int r=0;r for (int c=0;c float dec=float(rand()%precision)/precision;
m[r][c]=float(rand()%5)+1.0+dec;
}
}

int _tmain(int argc, _TCHAR* argv[])
{
srand((unsigned)time(NULL));

//save/load from file7
Matrix a(5,5);
init_matrix(a);
a[0][0]=-13;
a[1][1]=-13;
cout < < “Writing to file from Matrix a:” < cout << a< ofstream of;
of.open(“test.txt”);
of << a< of.close();
ifstream iff(“test.txt”);
if (!iff) {
cout << “Error opening file”< return 1;
}
Matrix b;
cout < < “Reading from file into Matrix b:”< iff >> b;
iff.close();
cout < cout << b<

cout <<“Press any key to continue…”< getchar();

//add two floating-point matrices
Matrix c(3,2);
init_matrix(c,100);
cout < <“Matrix c:”< Matrix d(3,2);
init_matrix(d,100);
cout < < “Matrix d:”< cout << “c+d:”<

cout <<“Press any key to continue…”< getchar();

//scale a floating-point matrix
Matrix e(10,10);
init_matrix(e,1);
float scalar=-1.5;
cout < < “Matrix e:” << endl< cout << “Scalar: “< cout << “e * scalar:”<

cout <<“Press any key to continue…”< getchar();

//matrix-product
Matrix<__int64> f(3,5);
Matrix<__int64> g(5,6);
init_matrix(f);
init_matrix(g);
cout < <“Matrix f:”< cout <<“Matrix g:”< cout <<“f*g:”<

cout <<“Press any key to continue…”< getchar();

return 0;
}
[/code]

Conclusion

Operator overloading can be a powerful programming tool when it increases usability and understandability of a class. In this case, it’s much nicer to write matrix[0][4] rather than matrix->GetRow(0)->GetCol(4). However, it must always be remembered that overloading serves to make programming easier–it doesn’t benefit the end user at all. Overloading an operator must make sense, as I hope all of the decisions I made in this class make sense. If it’s appropriate, go ahead and use it. If it will make people wonder what you meant, than it’s probably something to stay away from.

Also, because this is a template, you could possibly have a matrix of any object, including, for example strings. This will work perfectly in some situations, but not in others. Basically, if + is defined on strings, then you can do matrix addition on a string matrix. However, * is usually not defined for strings, so a statement with that would refuse to compile.
[code lang=”cpp”]
Matrix s(2,7);
Matrix t(2,7);

/*
will work fine–concatenates strings
at same locations in matrix
*/
Matrix u=s+t;

Matrix v(7,5);
/*
will not compile: error C2676: binary ‘*’ :
‘std::string’ does not define this operator or a conversion to a type
acceptable to the predefined operator
*/
Matrix w=s*v;
[/code]

I did not make use of the — and ++ unary operators in this tutorial because they don’t always make sense when used on a matrix. With these operators it is important to know that since they can be both prefix and postfix, each version has a slightly different function signature. With the understanding you have gained in this tutorial, you should be able to look up how to implement these operators without trouble.

Hope this helps somebody understand this subject better! Happy coding!


Check out my latest book, the essential, in-depth guide to performance for all .NET developers:

Writing High-Performance.NET Code, 2nd Edition by Ben Watson. Available for pre-order: