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

Conclusion

This tip provides a new boolean random generator for VB which uses a more uniformly random technique than the existing random generator.