So, what have I been up to?
A week or so ago I encountered Andrew, a friend from last semester's Ordinary Differential Equations class, working on a program to generate prime numbers by going through a loop of odd integers and checking each for primality. Guh, that's going to take something like Σ π(n) operations. Since we know that n / ln(n) is a rough lower bound on π(n), his method was doing worse than O(n^2/ln(n))!
Since what he really wanted was a large number of primes, not to check one specific prime number I introduced him to the Sieve of Eratosthenes , and only briefly mentioned the few sieves I know of for primality testing ( quadratic , GNF ). With the Sieve of Eratosthenes you can determine if all the numbers from 3 to n are prime or not in only O(n) time. The trade-off being that it requires O(n) space (though this can be as low as 1 bit per number if you use bitpacking properly).
He decided to implement it in Java, so I decided to implement it in C. Then we wanted a visualization of it, so we both added that to our programs. We decided on some run length, and then just wrapped our abbreviated number line into a square. Heres what it looks like for a 120 by 120 grid:
Seeing all those dots like that, I figure maybe something cool would come of it if we implemented Conway's Game of Life too. I thought that it wouldn't die out. I thought, "Maybe when the run length has a lot of factors, but if we make it prime then there won't be the blank columns." Andrew thought that no matter what I did, the grid would not turn into anything but a blank screen. As it turns out, I was right :D Even with heavily composite widths the game produces interesting outcomes.
I knew that Golly was a popular game of life simulator, and I knew that it had implemented the very neat Hashlife algorithm for simulating really fast. I also knew that it uses quadtrees to store the (limited in size only by memory available) world. Knowing these things, I set off to make my implementation faster. I wanted tangible results fast, so I took the easy way out first. I changed from using an entire char for each cell to using a single bit, packed into a char. Then I refactored a lot of the code. Somewhere in here I split my project into two. I now had seratosthenes to generate prime numbers and output them into Golly's .rle file format. [Recognize RLE? So did I. Turns out it is named that because the format uses run length encoding ] I also now had clife to load up a very constrained subset of proper .rle files and simulate life on them. Lots of fun! Now, I wanted speed! What was the easiest way to get speed? Use pthreads to use all the cores on my machine, of course. This wasn't nearly as hard as I thought it might be. One commit later and I was in business. Now, it is hardcoded to use four threads because I did not want to figure out how to divide the board into equal sized pieces for, say, seven threads. So, four it is. The only issue which I thought I might run into was the fact that eight cells were packed into one char, and the update function was not atomic. So, I just made sure that the boundaries of the board splits fell onto boundaries of char splits. Some minor control additions and zooming, and it is a half-usable program at this point.
As to real life, well... I'm not nearly as proficient at it as I am at more purely theoretical things. Someday I'll buy some land with a river on it, user the hydroelectric power it provides and become as complete a hermit as possible. With some nice, outdated computers to experiment on, of course!