Pseudo-random number generator
|
This article may require cleanup to meet LifeWiki's quality standards. |
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] Elements of the p46-based one's output are defined by a recurrence relation involving the EQV operation (a glider is outputted only if the two inputted are equal), whereas the p120 one involves the XOR one (outputted only if they're different), and inverting the glider presences in either, replacing its XOR with EQV or vice versa and inverting its output will not change its output. A loop of n spaceships has 2n possible states, but the all-empty state in the case of XOR (and the all-full state in the case of EQV) will lead back into themselves, so the other states' periods are p<=2**n-1.[n 2] It is conjectured that p=2**n-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 print((lambda m,l: (__import__('sys').setrecursionlimit(1<<m),(lambda g,s: ('\n'*(2-l)).join(map(lambda n: str((lambda f: f(f))(lambda f: lambda c,i,o,p: (lambda o: 'A('+s(m,n)+')='+str(o)+': '+', '.join(map(lambda g: (str(len(tuple(g[1]))) if l else s(m,g[0])+': ('+','.join(map(lambda g: '('+str(g[0])+','+str(g[1][1])+')',g[1]))+')'),__import__('itertools').groupby(sorted(enumerate(zip(c,map(lambda i: g(n,i),range(1<<n)))),key=lambda x: x[1][0]),key=lambda 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))))(lambda n,i: i<<1&(1<<n)-1|i&1^i>>n-1,lambda n,k: ' '*(len(str(n))-len(str(k)))+str(k)))[1])(10,False)), the 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 maths paper by Laurent Bartholdi.
