Rule 30 RNG
April 29, 2011
We have examined several different random number generators in past exercises, including Donald Knuth’s lagged-fibonacci generator that is used in the Standard Prelude. We also looked at cellular automata in a previous exercise. In today’s exercise we combine random number generators and cellular automata by looking at a random number generator developed by Stephen Wolfram, based on the Rule 30 cellular automaton of his book A New Kind of Science. Our random number generator will be similar to that in Mathematica; it is not cryptographically secure, but is suitable for simulation, as long as you avoid the occasional bad seed, like 0.
The cellular automata we are discussing have a state consisting of a row of cells; each cell can be in either of two states, 0 or 1. Unlike the cellular automata of the previous exercise, the row contains a finite number of cells and is considered to “wrap around” at the ends. A new state is generated based on the current state by assigning to each cell in the new state a value determined by the same-indexed cell in the previous state as well as the two cells immediately adjacent to it. The chart below shows the rule that determines the cell value in the new state:
| ■ ■ ■ | ■ ■ □ | ■ □ ■ | ■ □ □ | □ ■ ■ | □ ■ □ | □ □ ■ | □ □ □ |
| □ | □ | □ | ■ | ■ | ■ | ■ | □ |
The name Rule 30 comes from the binary-to-decimal conversion of the new values in each of the cells. Taking the same-indexed cell in each successive state gives a sequence of random bits; collect enough of them and you can convert them to a number.
In Wolfram’s book, the various cellular automata are studied based on an infinite row that starts with a single 1-cell, with all remaining cells having a value of 0; the successive states of that cellular automaton are shown in the image above-right. In a random-number generator, the initial state is seeded with 1s and 0s in some user-defined pattern.
Your task is to write a random-number generator based on the Rule 30 cellular automaton. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 