Life, part 30

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 is here.

And holy goodness again: it is August. In a normal year I'd be taking the month off from blogging and traveling to see my family, but thanks to criminally stupid coronavirus response, here I am, working from home. I suppose it could be a lot worse; I am glad to still have my health.

When last we left off we had computed whether each of 32 regions" of the eight Quad3s in a Quad4 were active (they had changed at least once cell since the previous tick of the same parity), stable (no change), or dead (stable and also all dead cells).

How can we make use of this to save on time?

Let's suppose we are currently in an even generation, call it K, and we are about to step the northwest Quad3 to get the new Quad3 and state bits for odd generation K+1. Under what circumstances could we skip doing that work? Let's draw a diagram:

The green square is oddNW, which is what we are about to compute. If any of the light blue shaded even" regions are marked as active then the green odd" Quad3 in generation K+1 might be different from how it was in generation K-1. The only way to find out is to execute the step and compare.

But now suppose all the light blue shaded regions are marked as either dead or stable. Remember what this means: in generation K-1 we compared the even Quad3s that we had just computed for generation K to those we had in hand from generation K-2. If all of those cells did not change from generation K-2 to generation K on the even cycle, then generation K+1 will be the same as generation K-1 on the odd cycle, so we can skip doing all work! (Note: the all work" is a small lie. Do you see why? We'll come back to this point in a moment.)

What is that light blue shaded region? It is the entirety of evenNW plus the north 8*2 edge of evenSW, the west 2*8 edge of evenNE, and the northwest corner of evenSE. We have a uint that tells us with a single bit operation whether any of those regions are active, but you know what I'm like; I'm going to put it in a descriptive helper:

 private bool EvenNorthwestOrBorderingActive => (evenstate & 0x08020401) != 0x08020401;

And then a method that describes the semantics with respect to the odd generation:

private bool OddNWPossiblyActive() => EvenNorthwestOrBorderingActive;

And only then am I going to add it to our step function:

private void StepEvenNW(){ if (OddNWPossiblyActive()) { Quad3 newOddNW = Step9Quad2ToQuad3Even(...); OddNWState = oddNW.UpdateOddQuad3State(newOddNW, OddNWState); oddNW = newOddNW; }

And presto, we just did a small number of bit operations to determine when we can avoid doing a much larger number of bit operations! That's a win.

I said before that I lied when I said we could avoid all work; we still have some work to do here. (Though in the next episode, we'll describe how we really, truly can avoid this work!) The problem is: the odd NW quad3 probably still has regions marked as active, and that will then cause unnecessary work to get done on the next tick. If the condition of the if statement is not met then we know that this Quad3 is either stable or dead without having to compute the next generation and compare but we still have to set the Quad3 state bits as though we had.

 else { OddNWState = oddNW.MakeOddStableOrDead(OddNWState); }}

We do not have that method yet, but fortunately it is not difficult; we need to do only the work to distinguish dead from stable. We add a method to Quad3:

public Quad3State MakeOddStableOrDead(Quad3State s){ s = s.SetAllRegionsStable(); if (SoutheastCornerDead) s = s.SetCornerDead(); if (SouthEdgeDead) s = s.SetHorizontalEdgeDead(); if (EastEdgeDead) s = s.SetVerticalEdgeDead(); if (AllDead) s = s.SetAllRegionsDead(); return s;}

Super. All that remains is to work out for each of the remaining seven step functions, what regions do we need to check for activity, then make an efficient bit operation that returns the result. For example, suppose we wish to know if the odd SW Quad3 could possibly be active this round:

private bool OddSWPossiblyActive() => EvenSouthwestOrBorderingActive || S != null && S.EvenNorthEdge10WestActive;

That is: if the evenSW Quad3 is active, or the 2*8 eastern edge of the evenSE is active, or the 10*2 western side of the north edge of the Quad4 to the south is active. Of course those are:

private bool EvenSouthwestOrBorderingActive => (evenstate & 0x00080004) != 0x00080004;private bool EvenNorthEdge10WestActive => (evenstate & 0x02000100) != 0x02000100;

I know I keep saying this, but it is just so much more pleasant to read the code when it is written in English and the bit operations are encapsulated behind helpers with meaningful names.

Anyways, we have eight helper methods that determine whether a 10*10 region is active, and if not, then we skip stepping and instead mark the regions as stable or dead; I won't write them all out. Let's take it for a spin:

Algorithm time(ms) ticks size(quad) megacells/sNaive (Optimized): 4000 5K 8 82Abrash (Original) 550 5K 8 596Stafford 180 5K 8 1820Proto-QuickLife 1 770 5K 8 426Proto-QuickLife 2 160 5K 8 2050

HOLY GOODNESS; NEW RECORD!

We are now 25 times faster than our original naive implementation.

But wait, there's more! We still have not quite implemented the QuickLife algorithm. There are still three problems left to solve:

• We do not yet have an O(changes) solution in time. On each tick we examine each of 256 Quad4s; we do very little work for the stable ones, we do a little bit of work for the active ones, but we are still doing work for every Quad4. Can we do no work at all for the stable or dead Quad4s? That would give us a speed win.
• We do not yet have an O(living) solution in space. An all-dead Quad4 takes up just as much space as any other. Can we deallocate all-dead Quad4s? That would give us a space win.
• We still are not taking advantage of the sparse array of Quad4s to dynamically grow the board into the 20-quad we logically have available to us; we're trapped in a tiny little 8-quad still. Can we dynamically grow the board to support large patterns?

Next time on FAIC: Yes we can do all those things. But you know what we need? More bits to twiddle, that's what we need.