Here we go again! Fellow BASIC enthusiast Jeff “Coding Horror” Atwood, of Stack Overflow and Discourse fame, has started a project to translate the programs in the 1978 classic BASIC Computer Games into more modern languages. I never had a … Continue reading →
#conwayslife
38 posts
17 Feb 2021
12 Oct 2020
All right, let’s finish this thing off and finally answer the question that I’ve been asking for a while: are there any Life patterns that have unbounded quadratic growth? (Code for this final episode is here.) The answer is yes; … Continue reading →
6 Oct 2020
This was supposed to be the last episode of this series, but while writing it I discovered a bug in my implementation of Hensel’s QuickLife algorithm. It’s a small defect, easily fixed, but I thought it might be interesting to … Continue reading →
14 Sept 2020
Last time we implemented what looked like Gosper’s algorithm and got a disappointing result; though the quadtree data structure is elegant and the recursive algorithm is simple, and even though we memoize every operation, the time performance is on par … Continue reading →
10 Sept 2020
All right, we have our quad data structure, we know how to get and set individual elements, and we know how to display it. We’ve deduplicated it using memoization. How do we step it forward one tick? (Code for this … Continue reading →
26 Aug 2020
Last time in this series we learned about the fundamental (and only!) data structure in Gosper’s algorithm: a complete quadtree, where every leaf is either alive or dead and every sub-tree is deduplicated by memoizing the static factory. Suppose we … Continue reading →
17 Aug 2020
All right, after that excessively long introduction let’s get into Gosper’s algorithm, also known as “HashLife” for reasons that will become clear quite soon. Since the early days of this series I’ve mostly glossed over the code that does stuff … Continue reading →
13 Aug 2020
Today we will finish off our implementation of Hensel’s QuickLife algorithm, rewritten in C#. Code for this episode is here. Last time we saw that adding change tracking is an enormous win, but we still have not got an O(changes) … Continue reading →
5 Aug 2020
Holy goodness, we are on part 30; I never expected this to go for so long and we have not even gotten to Gosper’s algorithm yet! We will finish up Hensel’s QuickLife algorithm soon I hope. Code for this episode … Continue reading →
3 Aug 2020
We’ve built the foundation of the QuickLife algorithm; now let’s make it go fast. This is going to be a longer episode than usual because we have a large volume of code to get through to perform a relatively straightforward … Continue reading →
30 Jul 2020
We now have enough gear to make a naïve “proto-QuickLife” implementation as a test to see (1) does it work at all? and (2) what is the performance compared to our other implementations at various levels of sophistication? Code for … Continue reading →
27 Jul 2020
We’re continuing with our deep dive into Alan Hensel’s QuickLife algorithm, rewritten in C# with an emphasis on clarity. When last we left off we had the following established: A Quad2 is an immutable wrapper around a ushort A Quad3 … Continue reading →
23 Jul 2020
Last time on FAIC we saw how we could start with nine 2-quads — a 12×12 grid of cells — and with only a handful of ands, ors and table lookups we could get an 8×8 grid of cells of … Continue reading →
20 Jul 2020
Let’s crisp up the problem from last episode. The problem for today’s episode is to write a method that takes these nine 2-quads: Computes these sixteen 1-quads: And returns these four 2-quads: Those four 2-quads form a 3-quad; I haven’t … Continue reading →
16 Jul 2020
When last we left off we had representations for 0-quads — a single bit — 1-quads — four bits in a row — and 2-quads — a wrapper data structure around an unsigned short that could extract single cells or … Continue reading →
13 Jul 2020
This series is getting much longer than I expected, but I’m having a great time, so let’s keep it going. I want to look at two more algorithms; for the next few episodes we’ll look at the brilliant and subtle … Continue reading →
9 Jul 2020
Code for this episode is here. So far in this series every algorithm we’ve attempted has been either O(cells) or O(changes) in time, and O(cells) in space. Going with a straightforward “big square with dead cells surrounding it” approach tends … Continue reading →
6 Jul 2020
Last time on FAIC I said that we were done with Stafford’s algorithm, but right after that went up I received a thoughtful email from David Stafford himself; he then introduced me to Michael Abrash and Terje Mathisen, who was … Continue reading →
2 Jul 2020
In today’s episode I want to again pause for a moment — this time, to verify that our allegedly O(change) implementation of Stafford’s algorithm really does have its performance gated on the number of cells changing in a tick. Here’s … Continue reading →
29 Jun 2020
Code for this episode is here. Today we can finish off our C# implementation of Stafford’s algorithm. Last time we turned the first pass into a table lookup; it might be a bit harder to optimize the second pass. Let’s … Continue reading →
25 Jun 2020
Code for this episode is here. A couple episodes back we did a first cut at implementing Stafford’s algorithm using the triplet data structure to store the current and upcoming states of three cells and their living neighbour counts, all … Continue reading →
22 Jun 2020
Code for this episode is here. We’ll take a short break from getting to our C# version of Stafford’s algorithm; in this episode I want to talk about some improvements to the UI, and also talk about some more fundamental … Continue reading →
18 Jun 2020
Source code for this episode is here. We are continuing with our project to gradually morph Abrash’s “remember the living neighbour counts” algorithm into Stafford’s algorithm. I’m going to start today by adding two very small bit-twiddling optimizations to the … Continue reading →
15 Jun 2020
Code for this episode is here. Where were we? I was gradually changing Abrash’s “remember the neighbour counts” into Stafford’s algorithm from an early 1990s optimization contest. In this series I’m going to illustrate the algorithm in C#, and we’ll … Continue reading →
11 Jun 2020
Source code for this episode is here. Before we get into today’s episode proper, a quick note. I’ve updated the client so that it now supports the ability to load a pattern off disk, execute that pattern, and “reset” back … Continue reading →
28 May 2020
Source code for this episode is here. Just as a reminder: I am developing my C# version of Stafford’s “QLIFE” algorithm by taking Abrash’s “keep the neighbour counts around” algorithm and gradually adding optimizations. That’s much easier to understand than … Continue reading →
26 May 2020
Code for this episode can be found here. Exciting news for the client; I have added a play/pause button. I suppose I could have added that single line of code earlier, but hey, better now than later. Last time on … Continue reading →
21 May 2020
Source code for this episode is here. I’ve added a panel to the UI that moves as the UI is resized; I’ll add some controls to it in future episodes. Back in 1994 I made a photocopy of an article … Continue reading →
18 May 2020
Last time on FAIC I discussed a technique for parallelizing computation of Life grids by using SIMD instructions to handle 256 bits worth of grid state truly in parallel. Today I’m going to not present an implementation, but rather discuss … Continue reading →
14 May 2020
Code for this episode can be found here, which — unusually — is not my GitHub repo. Last time on FAIC I mentioned that there were two basic techniques for improving raw performance: keep the algorithm the same but find … Continue reading →
11 May 2020
Last time on FAIC we took a look at Scholes’ extremely concise Life algorithm, which treats a grid as an array that you can treat as a mathematical value with some unusual but entirely straightforward manipulations. We didn’t get the … Continue reading →
7 May 2020
Code for today’s episode can be found here. I’ve added drag scrolling to the user interface, so if you click and hold, you can move around the grid much the same way that you’d move around an online map site. … Continue reading →
4 May 2020
Code for this episode can be found here. The only interesting change I’ve made to the client is that if you press “P”, it pauses the simulation and runs 5000 steps of the “acorn” pattern, and then dumps the number … Continue reading →
30 Apr 2020
Code for this episode can be found here. I have not added any more code to the engine, but the client now has two features of great use to me; pressing space toggles whether the simulation is running or paused, … Continue reading →
27 Apr 2020
Code for this episode can be found here. I have not updated the Life algorithm, but I have added a new feature to the client, namely, you can now resize the form and the display box will resize along with … Continue reading →
23 Apr 2020
Code for this episode can be found here. All right, let’s get into it. Since I want this series to concentrate on the algorithms and not the user interface, what I will probably do is make incremental improvements to the … Continue reading →
20 Apr 2020
Code for this episode can be found here. There are literally fifty years of articles explaining Conway’s Game of Life, starting with the one that introduced it to me: the October 1970 issue of Scientific American. Seems like a great … Continue reading →
13 Apr 2020
The mathematician John Horton Conway has died, apparently due to the covid-19 epidemic, at the age of 82. I never met him but by all accounts, he was a delightful person and brilliant mathematician; his charming book on introductory game … Continue reading →