Editing Hashlife (section)

===Representation===
The field is typically treated as a theoretically [[infinity|infinite]] grid, with the [[pattern (CA)|pattern]] in question centered near the [[origin (mathematics)|origin]]. A [[quadtree]] (with [[hash consing|sharing]] of nodes) is used to represent the field. A node at the ''k''th level of the tree represents a square of 2<sup>2''k''</sup> cells, 2<sup>''k''</sup> on a side, by referencing the four ''k''–1 level nodes that represent the four <math>2^{k-1} \times 2^{k-1}</math> quadrants of that level ''k'' square. For example, a level 3 node represents an 8×8 square, which decomposes into four 4×4 squares. Explicit cell contents are only stored at level 0. The root node has to be at a high enough level that all live cells are found within the square it represents.

While a quadtree naively seems to require far more [[computational overhead|overhead]] than simpler representations (such as using a [[matrix (mathematics)|matrix]] of [[bit]]s), it allows for various optimizations. Since each cell is either live or dead, there are only two possibilities for a node at level 0, so if nodes are allowed to be shared between parents, there is never a need for having more than 2 level 0 nodes in total. Likewise the 4 cells of a 2×2 square can only exhibit <math> 2^4 = 16 </math> different combinations, so no more than that many level 1 nodes are needed either. Going to higher levels, the number of possible ''k''th level squares grows as <math> 2^{2^k \cdot 2^k} = 2^{2^{2k}} </math>, but the number of distinct ''k''th level squares occurring in any particular run is much lower, and very often the same square contents appears in several places. For maximal sharing of nodes in the quadtree (which is not so much a [[tree (graph theory)|tree]] as a [[directed acyclic graph]]), we only want to use one node to represent all squares with the same content.