Difference between revisions of "HashLife"
m (added link to Tom Rokicki's early article on HashLife) |
m (red link removal) |
||
| (8 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
{{Glossary}} | {{Glossary}} | ||
[[File:Turing Machine in Golly.png|thumb|379px|right|The 6,366,548,773,467,669,985,195,496,000th (6 octillionth) generation of Paul Rendell's [[Turing machine]], computed in less than 30 seconds on an | [[File:Turing Machine in Golly.png|thumb|379px|right|The 6,366,548,773,467,669,985,195,496,000th (6 octillionth) [[generation]] of Paul Rendell's [[Turing machine]], computed in less than 30 seconds on an Intel Core Duo 2GHz CPU using HashLife in [[Golly]].]] | ||
'''HashLife''' is an algorithm created by [[Bill Gosper]] in 1984 for simulating the [[ | '''HashLife''' is an algorithm created by [[Bill Gosper]] in 1984 for simulating the [[Game of Life]]. It is designed to take advantage of the considerable amount of repetitive behaviour in many large [[pattern]]s of interest.<ref>R. Wm. Gosper, ''Exploiting Regularities in Large Cellular Spaces''. Physica '''10D''' (1984) 75-80.</ref> | ||
Roughly speaking, the idea of the algorithm is to store subpatterns in a hash table so that the results of their evolution don't have to be recomputed if they arise again at another place or time: 2<sup>N+1</sup>×2<sup>N+1</sup> tiles are run 2<sup>N-1</sup> ticks into the future, and the 2<sup>N</sup>×2<sup>N</sup> centers are stored and re-used without recalculating them, whenever the same large hashtiles show up again. This works because information cannot travel faster than the [[speed of light]]: it is impossible for anything outside of the large tile to affect the center area in that amount of time.<ref name="dvgrn20170711" /> | Roughly speaking, the idea of the algorithm is to store subpatterns in a hash table so that the results of their evolution don't have to be recomputed if they arise again at another place or time: 2<sup>N+1</sup>×2<sup>N+1</sup> tiles are run 2<sup>N-1</sup> ticks into the future, and the 2<sup>N</sup>×2<sup>N</sup> centers are stored and re-used without recalculating them, whenever the same large hashtiles show up again. This works because information cannot travel faster than the [[speed of light]] in Conway's Game of Life and other rules of range 1: it is impossible for anything outside of the large tile to affect the center area in that amount of time.<ref name="dvgrn20170711" /> | ||
This does, however, mean that complex patterns can require substantial amounts of memory. HashLife provides a means of evolving repetitive patterns millions (or even billions or trillions) of generations further than normal Life algorithms such as [[QuickLife]] can manage in a reasonable amount of time. It is not, generally, suitable for showing a continuous display of the evolution of a pattern, because it works asynchronously — at any given moment it will usually have evolved different parts of the pattern through different numbers of generations. Nonetheless, some Life simulation programs do have a HashLife mode, the most well-known example being [[Golly]]. | This does, however, mean that complex patterns can require substantial amounts of memory. HashLife provides a means of evolving repetitive patterns millions (or even billions or trillions) of generations further than normal Life algorithms such as [[QuickLife]] can manage in a reasonable amount of time. It is not, generally, suitable for showing a continuous display of the [[evolution]] of a pattern, because it works asynchronously — at any given moment it will usually have evolved different parts of the pattern through different numbers of generations. Nonetheless, some Life simulation programs do have a HashLife mode, the most well-known example being [[Golly]]. | ||
More detail on the quadtree data structure that underlies the HashLife algorithm and Golly's associated [[macrocell]] format can be found in Tomas Rokicki's 2006 article in Dr. Dobb's Journal.<ref name="trokicki20060401" /> | More detail on the quadtree data structure that underlies the HashLife algorithm and Golly's associated [[macrocell]] format can be found in Tomas Rokicki's 2006 article in ''Dr. Dobb's Journal''.<ref name="trokicki20060401" /> | ||
HashLife can be used for any [[outer-totalistic]] Life-like cellular automaton using the [[Moore neighbourhood|Moore]] or [[von Neumann neighbourhood]]s | HashLife can be used for any [[outer-totalistic]] [[Life-like cellular automaton]] using the [[Moore neighbourhood|Moore]] or [[von Neumann neighbourhood]]s; increasing the size of the base hashtiles allows it to be adapted to the larger neighborhoods of [[Larger than Life]] rules. | ||
==References== | ==References== | ||
| Line 22: | Line 22: | ||
}}</ref> | }}</ref> | ||
<ref name="trokicki20060401">{{cite web | <ref name="trokicki20060401">{{cite web | ||
|url = http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 | |url = https://web.archive.org/web/20120719224016/http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478 | ||
|title = An Algorithm for Compressing Time and Space | |title = An Algorithm for Compressing Time and Space | ||
|author = Tomas Rokicki | |author = Tomas Rokicki | ||
| Line 28: | Line 28: | ||
|accessdate = July 11, 2017 | |accessdate = July 11, 2017 | ||
|work = Dr. Dobb's Journal | |work = Dr. Dobb's Journal | ||
}}</ref> | }} (archived from the original on July 19, 2012)</ref> | ||
</references> | </references> | ||
| Line 34: | Line 34: | ||
{{LinkWeisstein|HashLife.html}} | {{LinkWeisstein|HashLife.html}} | ||
{{LinkLexicon|lex_h.htm#hashlife}} | {{LinkLexicon|lex_h.htm#hashlife}} | ||
{{LinkGollyHelp|filename=Algorithms/HashLife.html}} | |||
{{LinkWikipedia|Hashlife}} | {{LinkWikipedia|Hashlife}} | ||
[[Category:Algorithms]] | [[Category:Algorithms]] | ||
Revision as of 14:28, 12 May 2020
HashLife is an algorithm created by Bill Gosper in 1984 for simulating the Game of Life. It is designed to take advantage of the considerable amount of repetitive behaviour in many large patterns of interest.[1]
Roughly speaking, the idea of the algorithm is to store subpatterns in a hash table so that the results of their evolution don't have to be recomputed if they arise again at another place or time: 2N+1×2N+1 tiles are run 2N-1 ticks into the future, and the 2N×2N centers are stored and re-used without recalculating them, whenever the same large hashtiles show up again. This works because information cannot travel faster than the speed of light in Conway's Game of Life and other rules of range 1: it is impossible for anything outside of the large tile to affect the center area in that amount of time.[2]
This does, however, mean that complex patterns can require substantial amounts of memory. HashLife provides a means of evolving repetitive patterns millions (or even billions or trillions) of generations further than normal Life algorithms such as QuickLife can manage in a reasonable amount of time. It is not, generally, suitable for showing a continuous display of the evolution of a pattern, because it works asynchronously — at any given moment it will usually have evolved different parts of the pattern through different numbers of generations. Nonetheless, some Life simulation programs do have a HashLife mode, the most well-known example being Golly.
More detail on the quadtree data structure that underlies the HashLife algorithm and Golly's associated macrocell format can be found in Tomas Rokicki's 2006 article in Dr. Dobb's Journal.[3]
HashLife can be used for any outer-totalistic Life-like cellular automaton using the Moore or von Neumann neighbourhoods; increasing the size of the base hashtiles allows it to be adapted to the larger neighborhoods of Larger than Life rules.
References
- ↑ R. Wm. Gosper, Exploiting Regularities in Large Cellular Spaces. Physica 10D (1984) 75-80.
- ↑ Dave Greene (July 11, 2017). "Re: Larger than Life". ConwayLife.com forums. Retrieved on July 11, 2017.
- ↑ Tomas Rokicki (April 1, 2006). "An Algorithm for Compressing Time and Space". Dr. Dobb's Journal. Retrieved on July 11, 2017. (archived from the original on July 19, 2012)
External links
- HashLife at the Life Lexicon
HashLife at Golly's online help
- HashLife at Wikipedia