Pseudo-random number generator

A pseudo-random number generator (PRNG) is an algorithm that produces a sequence of bits that looks random (but cannot really be random, being algorithmically determined).

In Life, the term refers to a PRNG implemented as a Life pattern, with the bits represented by the presence or absence of objects such as gliders or blocks. Such a PRNG usually contains gliders or other spaceships in a loop with a feedback mechanism that causes later spaceships to interfere with the generation of earlier spaceships, in a linear-feedback shift register.^{[n 1]} PRNGs' outputs are usually defined by recurrence relations.

the p46-based PRNG is defined by b_n = b_n-1 EQV b_n-k, using the EQV operation (a glider is outputted only if the two inputted are equal),
the p120-based PRNG is defined by b_n = b_n-1 XOR b_n-k, using XOR (outputted only if they're different),

Inverting the glider presences in one is equivalent to swapping the operations XOR and EQV.

XOR and EQV are usually preferred over other logical operators, because they are bijective functions; when these recurrence relations are considered as functions on states k bits long, the graph of states is partitioned into cycles, whereas other operations would have branches leading into cycles.

A loop of n spaceships has 2ⁿ possible states, but the empty state in the case of XOR (and the full state in the case of EQV) will lead back into themselves, so the other states' periods are p ≤ 2ⁿ-1.^{[n 2]} It is conjectured that p = 2ⁿ-1 (so any non-empty state will lead to all others before reaching itself again) in the case that n is of the form 2^k-1.^{[n 3]}

Notes

↑ See also linear-feedback shift register on Wikipedia. Note that when these don't contain booleans (represented by gliders) but numbers, and each successive element is computed by a recurrence relation of adding multiples of the preceding ones, instead of applying boolean functions, it can be used to divide polynomials and thereby compute generating functions.
↑ A program for generating it is
__import__('sys').setrecursionlimit(1<<m);print((λ m,l: (λ g,s: ('\n'*(2-l)).join(map(λ n: str((λ f: f(f))(λ f: λ c,i,o,p: (λ o: 'A('+s(m,n)+')='+str(o)+': '+', '.join(map(λ g: (str(len(tuple(g[1]))) if l else s(m,g[0])+': ('+','.join(map(λ g: '('+str(g[0])+','+str(g[1][1])+')',g[1]))+')'),__import__('itertools').groupby(sorted(enumerate(zip(c,map(λ i: g(n,i),range(1<<n)))),key=λ x: x[1][0]),key=λ x: x[1][0]))) if all(c) else f(f)(c,c.index(0),o,p+1))(o+(c[i]==p)) if c[i] else f(f)(c[:i]+(p,)+c[i+1:],g(n,i),o,p))((0,)*(1<<n),0,0,1)),range(1,m))))(λ n,i: i<<1&(1<<n)-1|i&1^i>>n-1,λ n,k: ' '*(len(str(n))-len(str(k)))+str(k)))(10,False))
Τhe first parameter at the end determines the maximum value of n to search up to, and the second whether it returns a list of lengths (True) or explicit cycles (False). For n ≥ 1, there are no fixed points, the cycle beginning with the sequence (0,0,...,0,1) seems to have the maximum period p, which is divisible by all other cycles' periods. (Note that p's prime factorisation is not always given by these, because not all numbers of the form 2^{2^k-1}-1 (the lengths of the cycles given when n is of the form 2^k-1) are Mersenne primes.) The OEIS sequence giving maximum periods with respect to n is A046932.
↑ The cases of cycle lengths from the all-on state for n being of the forms 2^k and 2^k+1 comprised a problem in the 1996 International Mathematical Olympiad, and were analysed (together with the 2^k-1 case) in a paper by Laurent Bartholdi.

External links

Pseudo-random number generator at the Life Lexicon

[1] See also linear-feedback shift register on Wikipedia. Note that when these don't contain booleans (represented by gliders) but numbers, and each successive element is computed by a recurrence relation of adding multiples of the preceding ones, instead of applying boolean functions, it can be used to divide polynomials and thereby compute generating functions.

[2] A program for generating it is
__import__('sys').setrecursionlimit(1<<m);print((λ m,l: (λ g,s: ('\n'*(2-l)).join(map(λ n: str((λ f: f(f))(λ f: λ c,i,o,p: (λ o: 'A('+s(m,n)+')='+str(o)+': '+', '.join(map(λ g: (str(len(tuple(g[1]))) if l else s(m,g[0])+': ('+','.join(map(λ g: '('+str(g[0])+','+str(g[1][1])+')',g[1]))+')'),__import__('itertools').groupby(sorted(enumerate(zip(c,map(λ i: g(n,i),range(1<<n)))),key=λ x: x[1][0]),key=λ x: x[1][0]))) if all(c) else f(f)(c,c.index(0),o,p+1))(o+(c[i]==p)) if c[i] else f(f)(c[:i]+(p,)+c[i+1:],g(n,i),o,p))((0,)*(1<<n),0,0,1)),range(1,m))))(λ n,i: i<<1&(1<<n)-1|i&1^i>>n-1,λ n,k: ' '*(len(str(n))-len(str(k)))+str(k)))(10,False))
Τhe first parameter at the end determines the maximum value of n to search up to, and the second whether it returns a list of lengths (True) or explicit cycles (False). For n ≥ 1, there are no fixed points, the cycle beginning with the sequence (0,0,...,0,1) seems to have the maximum period p, which is divisible by all other cycles' periods. (Note that p's prime factorisation is not always given by these, because not all numbers of the form 2^{2^k-1}-1 (the lengths of the cycles given when n is of the form 2^k-1) are Mersenne primes.) The OEIS sequence giving maximum periods with respect to n is A046932.

[3] The cases of cycle lengths from the all-on state for n being of the forms 2^k and 2^k+1 comprised a problem in the 1996 International Mathematical Olympiad, and were analysed (together with the 2^k-1 case) in a paper by Laurent Bartholdi.

[n 1]

[n 2]

[n 3]

Pseudo-random number generator

Notes

See also

External links

Navigation menu

Search