Hashlife

Hashlife is a memoized

Memoization

In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs...

algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

for computing the long-term fate of a given starting configuration in Conway's Game of Life

Conway's Game of Life

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....

and related cellular automata

Cellular automaton

A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...

, much more quickly than would be possible using alternative algorithms that simulate each time step of each cell of the automaton. The algorithm was first described by Bill Gosper

Bill Gosper

Ralph William Gosper, Jr. , known as Bill Gosper, is an American mathematician and programmer from Pennsauken Township, New Jersey...

in the early 1980s while he was engaged in research at the Xerox Palo Alto Research Center. Hashlife was originally implemented on Symbolics

Symbolics

Symbolics refers to two companies: now-defunct computer manufacturer Symbolics, Inc., and a privately held company that acquired the assets of the former company and continues to sell and maintain the Open Genera Lisp system and the Macsyma computer algebra system.The symbolics.com domain was...

Lisp machine

Lisp machines were general-purpose computers designed to efficiently run Lisp as their main software language. In a sense, they were the first commercial single-user workstations...

s with the aid of the Flavors extension.

Hashlife is designed to exploit large amounts of spatial and temporal redundancy

Redundancy (information theory)

Redundancy in information theory is the number of bits used to transmit a message minus the number of bits of actual information in the message. Informally, it is the amount of wasted "space" used to transmit certain data...

in most Life rules. For example, in Conway's Life

Conway's Game of Life

The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....

, the maximum density of live cells in a region is only ½, and many seemingly random patterns end up as collections of simple still lifes

Still life (CA)

In Conway's Game of Life and other cellular automata, a still life is a pattern that does not change from one generation to the next. A still life can be thought of as an oscillator with unit period.-Pseudo still lifes:...

and oscillators

Oscillator (CA)

In a cellular automaton, an oscillator is a pattern that returns to its original state, in the same orientation and position, after a finite number of generations. Thus the evolution of such a pattern repeats itself indefinitely...

Representation

The field is typically treated as a theoretically infinite

Infinity

Infinity is a concept in many fields, most predominantly mathematics and physics, that refers to a quantity without bound or end. People have developed various ideas throughout history about the nature of infinity...

grid, with the pattern in question centered near the origin

Origin (mathematics)

In mathematics, the origin of a Euclidean space is a special point, usually denoted by the letter O, used as a fixed point of reference for the geometry of the surrounding space. In a Cartesian coordinate system, the origin is the point where the axes of the system intersect...

. A quadtree

Quadtree

A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This...

is used to represent the field. Given a square of 2^2k cells, 2^k on a side, at the kth level of the tree, the hash table stores the 2^k-1-by-2^k-1 square of cells in the center, 2^k-2 generations in the future. For example, for a 4x4 square it stores the 2x2 center, one generation forward; and for an 8x8 square it stores the 4x4 center, two generations forward.

Hashing

While a quadtree trivially has far more overhead

Computational overhead

In computer science, overhead is generally considered any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to attain a particular goal...

than other simpler representations (such as using a matrix

Matrix (mathematics)

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

of bit

Bit

A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...

s), it allows for various optimizations. As the name suggests, it uses hash table

Hash table

In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...

s to store the nodes of the quadtree. Many subpatterns in the tree are usually identical to each other; for example the pattern being studied may contain many copies of the same spaceship

Spaceship (CA)

In a cellular automaton, a finite pattern is called a spaceship if it reappears after a certain number of generations in the same orientation but in a different position...

, or even large swathes of empty space. These subpatterns will all hash

Hash function

A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...

to the same position in the hash table, and thus many copies of the same subpattern can be stored using the same hash table entry. In addition, these subpatterns only need to be evaluated once, not once per copy as in other Life algorithms.

This itself leads to significant improvements in resource requirements; for example a generation of the various breeders and spacefillers, which grow at polynomial

Polynomial

In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

speeds, can be evaluated in Hashlife using logarithmic

Logarithmic growth

In mathematics, logarithmic growth describes a phenomenon whose size or cost can be described as a logarithm function of some input. e.g. y = C log . Note that any logarithm base can be used, since one can be converted to another by a fixed constant...

space and time.

Superspeed and caching

A further speedup for many patterns can be achieved by evolving different nodes at different speeds. For example, one could compute twice the number of generations forward for a node at the (k+1)-th level compared to one at the kth. For sparse or repetitive patterns such as the classical glider gun

Gun (CA)

In a cellular automaton, a gun is a pattern with a main part that repeats periodically, like an oscillator, and that also periodically emits spaceships. There are then two periods that may be considered: the period of the spaceship output, and the period of the gun itself, which is necessarily a...

, this can result in tremendous speedups, allowing one to compute bigger patterns at higher generations faster, sometimes exponentially

Exponential growth

Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...

. To take full advantage of this feature, subpatterns from past generations should be saved

Cache

In computer engineering, a cache is a component that transparently stores data so that future requests for that data can be served faster. The data that is stored within a cache might be values that have been computed earlier or duplicates of original values that are stored elsewhere...

as well.

Since different patterns are allowed to run at different speeds, some implementations, like Gosper's own hlife program, do not have an interactive display, but simply compute a preset end result for a starting pattern, usually run from the command line. More recent programs such as Golly, however, have a graphical interface that can drive a Hashlife-based engine.

The typical behavior of a Hashlife program on a conducive pattern is as follows: first the algorithm runs slower compared to other algorithms because of the constant overhead associated with hashing

Hash function

A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...

and building the tree

Quadtree

; but later, enough data will be gathered and its speed will increase tremendously - the rapid increase in speed is often described as "exploding"

Exponential growth

Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...

Drawbacks

Like many memoized

Memoization

codes, Hashlife can consume significantly more memory

Computer memory

In computing, memory refers to the physical devices used to store programs or data on a temporary or permanent basis for use in a computer or other digital electronic device. The term primary memory is used for the information in physical systems which are fast In computing, memory refers to the...

than other algorithms, especially on moderate-sized patterns with a lot of entropy, or which contain subpatterns poorly aligned to the bounds of the quadtree nodes (ie. power-of-two sizes); the cache is a vulnerable component. It can also consume more time than other algorithms on these patterns. Golly, among other Life simulators, has options for toggling between Hashlife and conventional algorithms.

Hashlife is also significantly more complex to implement

Computer programming

Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...

. For example, it needs a dedicated garbage collector

Garbage collection (computer science)

In computer science, garbage collection is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program...

to remove unused nodes from the cache.

External links

HashLife from Eric Weisstein's Treasure Trove of Life
Tomas Rokicki's implementation of hashlife
- Golly -(cross-platform Windows/Linux/Mac successor program)
Entry in the Life Lexicon
Explanation of the algorithm from Dr Dobb's Journal
Gosper's Algorithm (Hashlife) Explained