Get best of the week

Generating pseudo-random numbers using a cellular automaton: Rule 30

Pseudorandom number generators give numbers deterministically, but usually such numbers look non-periodic (random). At least in most cases, the use of such numbers usually happens. The generator takes an initial value (ideally a true random number) and generates a sequence of numbers, working as a function of the initial value and (or) the previous number in the sequence. Such numbers are pseudo-random (and not true random numbers) due to the fact that if the initial value passed to the generator is known, these numbers can be generated again algorithmically. True random numbers are generated using special hardware or certain physical phenomena - pulse fluctuations in blood volume, atmospheric pressure, thermal noise, quantum processes, and so on.



There are many ways to generate pseudo random numbers. For example, the Blum – Blum – Shub algorithm , the mean square method , the Fibonacci method with delays . Today we will talk about generating random numbers using Rule 30 , which uses an ambiguous approach involving the use of a cellular automaton model . This method passed many standard random number tests and was used in Mathematica to generate random integers.

Cellular automaton


Before we get to the subject of Rule 30, let us take some time in cellular automata. A cellular automaton is a discrete model consisting of a regular grid of cells of any dimension. Each of the lattice cells can be in one of a finite set of states. Moreover, for each cell, such a concept as “neighborhood” is defined. In the vicinity of a certain cell, for example, all cells located at a distance of no more than 2 from it can enter. There are rules that determine how cells interact with each other and move on to the next generation (state). These rules are mainly represented by mathematical (programmable) functions, which depend on the current state of the cells and on the state of their neighbors.


Description of the cellular automaton The

description of the cellular automaton from the previous figure allows you to find out that each cell can be in one of two final states -0(shown in red) and1(shown in black). Each cell goes into the next generation, taking on a new state resulting from applying the operationXORto its 8 neighbors. The first generation (initial state) of the lattice is set randomly. The operation of this cellular automaton is shown below.


XOR-based

cellular automaton in action The idea of ​​a cellular automaton appeared in the 1940s thanks to Stanislav Ulam and John von Neumann . Cellular automata have found application in computer science, mathematics, physics, in the theory of complex systems, in theoretical biology, and in problems of modeling the microstructure of media and materials. In the 1980s, Stephen Wolfram conducted a systematic study of a one-dimensional cellular automaton (it is also called an elementary cellular automaton), on which Rule 30 is based.

Rule 30


Rule 30 is an elementary (one-dimensional) cellular automaton in which each cell can reside in one of two final states: 0(red cells in the figure below) and 1(black cells). The vicinity of the cell is represented by its two closest neighbors located to the left and right of it. The next state (generation) of a cell depends on its current state and on the state of its neighbors. The rules for transitioning cells to the next state are shown in the following figure.


Rule 30

These rules of transition to a new state of cells can be simplified written asleft XOR (central OR right).

We display the cells of the automaton in the form of a two-dimensional lattice, each row of which represents one generation (state). When the next generation (state) of cells is calculated, it is displayed below the last known state. Each row contains a finite number of cells that, in the end, “loop”.


Rule 30 in action

The above pattern arises from the initial state (line 0) when one cell has a state1(black) and all the cells surrounding it have a state0(red). The state of the cells in the next generation (line 1) is calculated according to the above rule. The vertical grid represents time, and the intersections of rows and columns represent the state of a particular cell at a particular stage in the development of the system.


Generation t and generation t + 1

As the pattern develops, red triangles of different sizes often appear in it, but, in general, a distinguishable pattern cannot be recognized in the resulting structure. The above fragment of the lattice is made at an arbitrarily chosen moment in time. Here you can see chaos and aperiodicity. This property is Rule 30 and is used to generate pseudo-random numbers.

Pseudo Random Number Generation


As already mentioned, Rule 30 demonstrates aperiodic and chaotic behavior. As a result, its application leads to the creation of complex, and, it seems, random patterns according to simple and well-defined rules. To generate random numbers using Rule 30, the central lattice column is used, from which a sequence of nrandom bits is selected , from which the desired n-bit random number is generated . The next random number is generated using the following nbits from the column.


Generating random numbers using Rule 30

If you always start selecting cells from the first line, then the generated sequence of numbers will always be predictable. And this is not what we need. In order to create pseudorandom numbers, we will use a random initial value (for example, the current time), skip the corresponding number of lines, and after that select sequences fromnlines and create random numbers based on them.

The pseudo-random numbers generated using Rule 30 are not cryptographically secure, but they are suitable for simulations - until we use inappropriate initial values ​​like0.

One of the major advantages of applying Rule 30 to generate pseudo-random numbers is that you can create many random numbers in parallel mode by randomly selecting many columns of length n bits. Here is an example of a pseudo-random sequence of 8-bit numbers generated by this method using the initial value 0: 220, 197, 147, 174, 117, 97, 149, 171, 240, 241.

The initial value, in addition, can be used to set the initial state of the model (line No. 0). As a result, pseudo-random numbers can be obtained simply by choosingnbit from the center column, starting at row zero. This approach is more effective, but it is highly dependent on the quality of the initial value. An incorrectly selected initial value can lead to the appearance of well-predicted numbers. A demonstration of this approach can be found here .

Rule 30 in the real world


Rule 30 can be seen in nature, in the form of a pattern on the shell of the gastropod species Conus textile . The Cambridge North train station is framed by panels depicting the evolutionary results of a model constructed using Rule 30.

Summary


If you find Rule 30 interesting, I recommend writing your own simulation using the p5 library . This algorithm can be implemented in a fairly general form, which will allow the same program to generate patterns for different rules - 90, 110, 117, and so on. Patterns generated using various rules are very interesting. If you want, you can go to the next level. You can expand the model to three dimensions and explore the evolution of patterns. I think that programming can bring a lot of pleasure if it has a visual component.

It is amazing when two seemingly unrelated fields of science, cellular automata and cryptography, combine to create something surprising. Although the algorithm described here is no longer widely used due to the emergence of more efficient algorithms, it encourages us to creatively use cellular automata.

Dear readers! What pseudo random number generators do you use?

More articles:


All Articles