{"id":1291,"date":"2006-07-23T10:57:23","date_gmt":"2006-07-23T14:57:23","guid":{"rendered":"http:\/\/mjtsai.com\/blog\/2006\/07\/23\/hashlife\/"},"modified":"2006-07-23T10:57:23","modified_gmt":"2006-07-23T14:57:23","slug":"hashlife","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2006\/07\/23\/hashlife\/","title":{"rendered":"HashLife"},"content":{"rendered":"<p>\r\n<a href=\"http:\/\/www.ddj.com\/dept\/ai\/184406478\">DDJ<\/a> on how Gosper used a clever representation and memoization of <em>multiple<\/em> levels of calls to get a huge speedup:\r\n<\/p>\r\n\r\n<blockquote cite=\"http:\/\/www.ddj.com\/dept\/ai\/184406478\">\r\n<p>\r\nMaking a slow program fast can lead to both joy and frustration.\r\nFrequently, the best you can do is a low-level trick to double or maybe\r\nquadruple the speed of a program; for instance, many readers may have\r\nimplemented John Conway&rsquo;s &ldquo;Game of Life&rdquo; using bit-level operations for\r\na significant speedup. But sometimes a whole new approach, combining\r\njust a few ideas, yields amazing improvements. A simple algorithm called\r\n&ldquo;HashLife,&rdquo; invented by William Gosper (&ldquo;Exploiting Regularities in\r\nLarge Cellular Spaces,&rdquo; <i>Physica 10D<\/i>, 1984), combines quadtrees\r\nand memoization to yield astronomical speedup to the Game of Life. In\r\nthis article, I evolve the simplest Life implementation into this\r\nalgorithm, explain how it works, and run some universes for trillions of\r\ngenerations as they grow to billions of cells. \r\n<\/p>\r\n<\/blockquote>","protected":false},"excerpt":{"rendered":"<p>DDJ on how Gosper used a clever representation and memoization of multiple levels of calls to get a huge speedup: Making a slow program fast can lead to both joy and frustration. Frequently, the best you can do is a low-level trick to double or maybe quadruple the speed of a program; for instance, many [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"apple_news_api_created_at":"","apple_news_api_id":"","apple_news_api_modified_at":"","apple_news_api_revision":"","apple_news_api_share_url":"","apple_news_coverimage":0,"apple_news_coverimage_caption":"","apple_news_is_hidden":false,"apple_news_is_paid":false,"apple_news_is_preview":false,"apple_news_is_sponsored":false,"apple_news_maturity_rating":"","apple_news_metadata":"\"\"","apple_news_pullquote":"","apple_news_pullquote_position":"","apple_news_slug":"","apple_news_sections":"\"\"","apple_news_suppress_video_url":false,"apple_news_use_image_component":false,"footnotes":""},"categories":[4],"tags":[],"class_list":["post-1291","post","type-post","status-publish","format-standard","hentry","category-programming-category"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/1291","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/comments?post=1291"}],"version-history":[{"count":0,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/1291\/revisions"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=1291"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=1291"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=1291"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}