Tomas Rokicki describes a very novel approach to implementing the game of life in “An algorithm for Compressing Time and Space“.

The Game of Life is an example of a cellular automata, in which the state of cells in a grid are updated based on the state of the surrounding cells. In the case of the game of life, a cell can be considered alive or dead, and from one generation to the next, a live cell dies if it has less than 2 or more than 3 neighbours, and a dead cell comes to life if it has exactly 3 neighbours. From these simple rules comes an incredible variety of behaviors mimicking the complexity of life itself, and inspiring both professional and amateur scientists to study the game.

A simplistic way to implement this game is to define a the current state as a large 2D array, then iterating across that array, examining neighbours and placing the new state into a new 2D array. This is an O(N) algorithm, where N is the number of cells in the grid. When the grid gets extremely large, and the number of generations of interests hits the billions or trillions mark, a better approach is called for.

Tomas’ clever approach is to recursively subdivide the grid into quarters (a quadtree), while memoizing the pattern in each subdivision. Identical subdivisions will iterate in an identical way. Handling of boundary conditions is a complication, the solution to which is described in detail in his article.

How this relates to functional programming is that iterating a subdivision is equivalent to a function on its state. The same function applied to the same argument gives the same result. By keeping a record of argument->result pairs, we can avoid computing the result more than once, for a possible speedup. This technique is called memoization.

Thomas goes on to memoize not only a single iteration, but multiple iterations for each subdivision, giving a further speedup.

The end result of this incredibly fast implementation the Game of Life can be found at http://golly.sourceforge.net/

Interestingly enough, I had recently been playing with a Game of Life implementation that runs on the GPU, but Golly beats the pants off a GPU implementation, thus proving the maxim that a better algorithm always beats better hardware.