I've written many programs for school and for fun. Some of the more more interesting are published here.
I've used C++, IA-32 assembly language, Mathematica and Matlab for various programming projects. For those who don't know, Mathematica and Matlab are proprietary languages geared made for mathematical work. Mathematica is both a symbolic and numerical language. As far as I know it is the best program for symbolic math all around, it is a pain to try and write a large program in. Matlab is strictly a numerical language, it comes with Maple (another symbolic math program), but Matlab itself is numerical. Matlab's advantage is that it come with huge number of mathematical functions and it handles matrices quite well. Unlike C++ which can be had for free, Matlab and Mathematica cost over $100 US for a student version and over $1000 US for professional versions. For intense mathematical work they are both very valuable. One real problem with Mathematica and Matlab is they are interpreted languages, making them slow for large programs. They both have options to compile the code before executing it, but at least for Mathematica, not all types of code can be compiled.
Knight's tour implemented in Matlab
The knight's tour is the first real program I ever wrote, I did so for fun, using C++. I still have the executable but have lost the original code. So, I rewrote it in Matlab. The board size is variable, this program uses the warnsdorff heuristic looking one move ahead. The knight's tour is a classic chess related problem. The problem is to move a knight to every single square on the board only once. Doing this randomly is nearly impossible, using something called the warnsdorff heuristic it becomes very easy. When I implemented this in C++ a run of 50000 tours gave a success rate 97.9%, on a standard 8 by 8 board. What the heuristic does is look at each square the knight can move to and from those squares count how many squares can be reached. The knight must then move to the square with the lowest score. This effectively gets the knight to get the hardest to reach squares first. The success rate can be improved by looking more than one square ahead, at the expense of more computation per move. The heuristic is not fool proof, as the above success rate shows, the heuristic can lead down down a blind alley. The heuristic also can fail more frequently for larger boards by cutting itself of and only getting to half the squares before being trapped. For someone trying to enumerate all possible routes of the knights tour this algorithm is not suitable. Since it is possible to complete a tour by making moves to squares that are easily accessible compared to other squares (in contradiction to the warnsdorff rules) this heuristic cannot create all possible tours. If the heuristic is modified so that all moves are made randomly unless a square must be moved to because another opportunity will not arise, then the algorithm would be capable of creating all possible tours.
The N-Queens problem is a generalization a the 8 queens problem. Here for an N by N board one must place N queens so that they don't attack each other. The parameter N is hard coded in thiis program. For the 8 by 8 case there are 92 solutions. The standard approach is to start a queen on the first row and column, then add queens and push them up each column to a safe spot, if a column is not safe the previous queen is moved up and so on. My algorithm and that of other programs I've seen has 4 vectors. One for y coordinates where the index is x, one of boolean values to indicate if a y value is already taken and two more for boolean values keeping track of which positive and negative diagonals are occupied. My program uses one byte for all these values, boolean or integer. I actually use char, since it is the only portable way to get a one byte int. However, my program uses inline assembly language to keep track of clock cycles used, this is obviously not portable. The boolean variables need not be one byte, one bit would suffice. I've written assembly code where I stuffed 4 one byte variables in a 4 byte register and accessed them separately by rotating the register. This saves potentially slow memory accesses. This could be done for this code, and would make it much faster, although much less readable. So, when I have time I may publish an optimized version. Since such an optimization would be easier with 64 bit registers due to the N sizes of interest (above 20). Since my PC is 32 bit, that won't be happening any time soon.
Mode 13H Graphics in IA-32 Assembly Language
As part of a group project to develop a game for the PC in intel assembly language I wrote several basic graphics procedures (a couple thousand lines). I am most proud of the _DrawLine function. It uses the bresenham line drawing algorithm to draw lines between any two (x,y) coordinates. Like all my other procedures all the variables were placed in registers. In the case of this algorithm I had to stuff several variables in one register and roll the register in order to access a given variable.
visitors since June 10th, 2005.
