The Population After a Billion Billion Generations
A ring of n cells runs the rule-table automaton of #2141: three values read
as left centre right give a position from 0 to 7, the bit of rule at that
position is the cell's next value, the ring wraps, and all cells change
simultaneously.
Print how many cells are alive after exactly g generations. Generation 0 is
the starting row, so if g is 0 the answer is the starting population.
The catch is the size of g. It reaches 10^18, and n is at most 16, so
stepping the automaton g times is not an option and never will be: at a
billion generations a second it would take about thirty years.
n = 5, rule = 90, g = 0, row = 00100 -> 1
n = 5, rule = 90, g = 7, row = 00100 -> 2
n = 16, rule = 204, g = 10^18, row = 1011001011010110 -> 9
The last one is answerable by hand. Rule 204 has bits set exactly at the four
positions whose centre value is 1, so the rule copies the centre and nothing
ever changes. The population is the starting population, 9, for every g.
## What most people try first
A loop that runs g generations. It is correct and it cannot finish. The
second attempt is usually to look for a formula in n, rule and g, which
does not exist: the rule table is arbitrary and the behaviour across the 256
rules has no closed form.
## The state space is tiny, which is the whole opening
A generation is n bits with n at most 16, so there are at most 65536
possible rows. The step is a function of the current row alone. So among
generations 0, 1, ..., 65536 two must be equal by the pigeonhole principle,
and once a row repeats everything after it repeats, forever. The sequence of
generations is a TAIL of rows that happen once, followed by a LOOP that goes
round for ever:
gen: 0 1 2 ... s-1 | s s+1 ... s+p-1 | s s+1 ...
[----- the tail ----] [-- the loop, length p --] [ again ...
So instead of g steps, take at most 65537 of them and record where each row
first appeared. That gives s and p, exactly as in #2143. Then:
if g < s: the answer is generation g, which is in the tail, already recorded
otherwise: generation g equals generation s + ((g - s) mod p)
Count the set bits of that row.
## Why the reduction is correct
Write step for the function taking one generation to the next, so generation
k is step applied k times to generation 0. The loop found above means
generation s + p equals generation s. Applying step to both sides i
times gives generation s + p + i equals generation s + i for every i at
least 0, since step is a function and equal inputs give equal outputs. By
induction on j, generation s + i + j p equals generation s + i for every
j at least 0.
Now take any g at least s. Write g - s = q p + m with 0 <= m < p, which
is division with remainder. Then g = s + m + q p, so generation g equals
generation s + m, and s + m is below s + p, which is a row already
recorded. For g below s the row was recorded directly. So every g is
answered from the recorded prefix, and the prefix has at most 65537 entries.
## Overflow, and the one language that needs care
g reaches 10^18, which is far past the signed 32 bit limit of 2147483647,
so it must be read into a 64 bit type. Signed 64 bit reaches about
9.2 * 10^18, so 10^18 fits with room to spare, and no intermediate value
grows: (g - s) mod p is computed directly from values already in range.
JavaScript is the exception. A plain Number is exact only below 2^53, which
is about 9.007 * 10^15, so 10^18 read as a Number is NOT the value in the
input, and (g - s) % p on it gives a silently wrong remainder. Read g as a
BigInt, do the subtraction and the remainder in BigInt, and only then
convert the result, which is below p and so below 65537, back to a Number
for use as an index. Note also that the row masks are at most 16 bits, so the
bitwise operators used on THEM are exact and need no BigInt.
## Cost
At most 2^n + 1 steps of O(n) each to find the tail and the loop, so
O(n 2^n) time and O(2^n) memory, independent of g. At n = 16 that is
about a million cell updates whether g is 7 or 10^18.