Generating Random Boolean Sequences Using Cellular Automata
Get more randomness with this mathematical technique
This tip demonstrates how to generate a sequence of random boolean numbers using a cellular automata technique described in Stephen Wolfram's book "A New Kind Of Science". Unlike many other linear congruential generators, the output of this method has been shown to be free of repetition and statistically random.
Cellular Automata As Random Number Generators
Cellular Automata are systems in which the current state is captured in a series of cells. The next state of the system is then generated from the current state by application of simple rules which determine the new state of a cell based on the states of its neighbours. One of the simplest forms of this type of system uses a one-dimensional array of cells, and considers only the current cell and its immediate neighbours to the left and the right to determine the next state. Despite the simplicity of the rule, there are a number of rules which lead to extremely complex behaviour. As a consequence the output is a good candidate for use in generating random numbers.
Typically, computer systems use a shift register type approach to generating numbers, like the one described in the article Generating long sequences of random numbers. Analysis of the output of these generators has shown that the output isn't as random as it ought to be. If the numbers are plotted against previously generated numbers in one, two or three dimensions then stripes begin to appear in the output, whereas a truly random sequence would be distributed.
Class 30 One Dimensional Cellular Automata
In Wolfram's book, all the possible one dimensional cellular automata with two states are given a number (there are 256 of them). Class 30 is one of the four which generates complex non-repetitive behaviour, and that is used here. This automata has the following rules:
IF [cell - 1] = black THEN IF [cell] = black OR [cell + 1] = black THEN newCell = white ELSE newCell = black ENDIF ELSE IF [cell] = black OR [cell + 1] = black THEN newCell = black ELSE newCell = white ENDIF ENDIF
A diagram of the output of this automata when the initial condition is a single black square is shown in the diagram below:
Class 30 Cellular Automata Output - 32 Iterations
The centre squares, highlighted in blue are used to generate the random heads/tails result.
To completely generate the output of the algorithm, an infinite cellular space would be needed (since new cells are continually generated to the right of any previous cell). In practice, the size of the cellular space can be restricted to a much smaller number, typically around 200 and the cellular space wrapped around (so that the neighbour to the right of the rightmost cell is the leftmost cell and similarly for the leftmost cell).
Therefore to implement the algorithm we need two arrays of 200 cells each: one to hold the current state, and another to hold the next state. The version provided here uses a two dimensional array to hold the current and next states, and simply swaps the index between the two blocks at each generation. Here's the algorithm:
Private m_lSize As Long Private m_cells() As Byte ' Using byte even though only two states needed Private m_iIndex As Long Public Function nextRandom() As Boolean ' determine the index to write into Dim iNextIndex As Long If (m_iIndex = 1) Then iNextIndex = 0 Else iNextIndex = 1 End If ' Calculate the automata Dim i As Long Dim iPrev As Long Dim iNext As Long iPrev = m_lSize - 1 For i = 0 To m_lSize - 1 iNext = (i + 1) Mod m_lSize If (m_cells(m_iIndex, iPrev) = 0) Then ' output is white if me or next is black: If (m_cells(m_iIndex, i) = 0) Or (m_cells(m_iIndex, iNext) = 0) Then m_cells(iNextIndex, i) = 1 Else m_cells(iNextIndex, i) = 0 End If Else ' output is black if me or next is black: If (m_cells(m_iIndex, i) = 0) Or (m_cells(m_iIndex, iNext) = 0) Then m_cells(iNextIndex, i) = 0 Else m_cells(iNextIndex, i) = 1 End If End If iPrev = i Next i m_iIndex = iNextIndex nextRandom = m_cells(iNextIndex, m_lSize \ 2) End Function Private Sub Class_Initialize() m_lSize = 200 ReDim m_cells(0 To 1, 0 To m_lSize - 1) As Byte m_iIndex = 0 ' seed the initial state m_cells(m_iIndex, m_lSize \ 2) = 1 End Sub
Of course, since the initial state is always the same this algorithm will always yield the same output. To allow different outputs, different starting conditions can be used by seeding the generator (similar to the Randomize method in VB. Two methods are provided in the code: firstly one which takes a long value, and centres values of each of the 32 bits into the array, and secondly one which takes a byte array, which can be used to set longer initial seeds:
Public Sub Seed(ByVal fSeed As Long) ' determine the index to write into Dim iNextIndex As Long If (m_iIndex = 1) Then iNextIndex = 0 Else iNextIndex = 1 End If ' write the bits: Dim lCentre As Long lCentre = m_lSize \ 2 Dim i As Long Dim j As Long Dim pow As Long pow = 1 j = lCentre - 16 For i = 0 To 31 If (j >= 0) And (j < m_lSize) Then m_cells(iNextIndex, j) = ((fSeed And pow) = pow) End If j = j + 1 If (i >= 30) Then pow = &H80000000 Else pow = pow * 2 End If Next i m_iIndex = iNextIndex End Sub Public Sub SeedLarge(b() As Byte) ' determine the index to write into Dim iNextIndex As Long If (m_iIndex = 1) Then iNextIndex = 0 Else iNextIndex = 1 End If Dim lSeedSize As Long lSeedSize = UBound(b) - LBound(b) + 1 Dim j As Long For j = 0 To lSeedSize - 1 m_cells(iNextIndex, j) = IIf(b(j + LBound(b)) > 0, 1, 0) If (j > m_lSize) Then Exit For End If Next j m_iIndex = iNextIndex End Sub
This tip provides a new boolean random generator for VB which uses a more uniformly random technique than the existing random generator.