The Second Insight

What are the most likely bits that we can do without? How about the life/death status bits for the current generation or the next generation? They take up four bits each and eliminating either one would put me just one bit short of my goal.

We can eliminate the current generation bits by placing them in the change-list. Just pack them in the same dword along with the cell address. There's still 28 bits left for the cell address which will permit a maximum grid size of 2^15 x 2^15 or 32,768 x 32,768. That's plenty.

After a cell is added to the change-list (and the current generation bits are copied as part of it) the current generation bits are updated to reflect the next generation status. This keeps cells from ever being added to the change-list twice.

Ok, we’re down to 17 bits now and one to go! Where will that last bit come from? We could get rid of the edge bit but that means either placing it in a separate table or calculating it at run-time. A separate, parallel table is probably not unreasonable. Calculating the edge status from the cell address would cost many cycles per cell. It would be much better to find the bit elsewhere.

On to Part 4. The third insight

Back to the main page