256-state cellular automaton

Anthony Pasqualoni

October 3, 2006

This report describes a 256-state cellular automaton that serves as a
random number generator. The automaton is compared with four random
number generators in the GNU Scientific Library: `taus`

,
`gfsr4`

, `mt19937`

, and `ranlxd1`

.
Statistical tests for randomness based on the Diehard test suite show
that the automaton is comparable to the GSL generators. In terms of
speed, the automaton generates random sequences at more than three
times the rate of the fastest GSL generator among those specified
above.

The automaton was discovered using genetic programming and a modified random search.

- Design and operation of the automaton
- Results
- Conclusion
- Files: source code and output
- Acknowledgments
- References

Random number sequences are generated using a one-dimensional cellular automaton with 256 states. Each cell is updated by adding its state to an adjacent cell's state, with the sum being used as an index in the automaton's rule table. The result of the table lookup is the cell's next state. Null boundary conditions are used: the left neighbor of cell 0 (the leftmost cell) is set to a constant state of zero.

The automaton comprises a row of 2046 cells, with each cell represented as a byte in a one-dimensional array. Since each cell comprises eight bits, four adjacent cells produce a 32-bit integer.

After a seed is used to set the initial cell values, the automaton is evolved by using a simple procedure. A pointer is used to keep track of the current cell. When an integer is requested, the current cell plus the next three cells are updated using the rule table. The pointer is shifted by four bytes, and the updated bytes are cast as an unsigned integer, which is the value returned. If the pointer has reached the last location in the array, it is moved to the first cell location, and the procedure is repeated.

An automaton with 256 states is used because only one cell update is needed to produce 8 bits in the random sequence. This results in the automaton being much more efficient than automata with fewer states. In comparison, each cell in an elementary automaton with two states represents one bit, so 32 cell updates are needed to produce an unsigned integer. With 256 states, only 4 cell updates are needed. This greatly reduces the amount of operations needed to produce a 32-bit integer.

The cellular automaton was compared with four random number generators
from version 1.8 of the GNU Scientific Library: `taus`

,
`gfsr4`

, `mt19937`

, and
`ranlxd1`

. According to the Random Number Generator
Performance page at the GSL Web site, `taus`

,
`gfsr4`

and `mt19937`

are the fastest simulation
quality generators among the selected set, and those based on the
`ranlux`

algorithm offer the best mathematically-proven
quality [1].

Comparisons between the cellular automaton and the GSL random number generators in terms of speed and quality of randomness are shown below.

The cellular automaton outperforms the GSL random number generators, being more than three times as fast as the GSL generators.

The following table shows the mean time for 10 runs of each generator, with each run producing 10 million integers. Source code for both the GSL generators and the cellular automaton was compiled using GCC version 4.1.0 with the -O2 optimization flag.

RNG: Mean time to produce 10 million integers: cellular automaton 0.062000 seconds gsl_rng_taus 0.200000 seconds gsl_rng_gfsr4 0.200000 seconds gsl_rng_mt19937 0.223000 seconds gsl_rng_ranlxd1 2.652000 seconds

Diehard, a battery of statistical tests developed by George Marsaglia, was used to measure randomness. Diehard was run on 100 sequences of 32-bit integers. Each sequence comprises 10 million integers generated with a random seed. Since Diehard produces 229 test results (p-values) for each sequence, a total of 22,900 p-values were determined for each random number generator.

A Python script was used to parse the Diehard results file. Results are shown below.

RNG: Failed tests: cellular automaton 13 of 22900 gsl_rng_taus 11 of 22900 gsl_rng_gfsr4 18 of 22900 gsl_rng_mt19937 13 of 22900 gsl_rng_ranlxd1 16 of 22900

A test is considered failed if it produces a p-value less than or equal to 0.0001 or greater than or equal to 0.9999. This results in a 95% confidence interval of p-values between 0.0001 and 0.9999 [2,3].

In addition to the standard set of tests, Diehard includes three additional tests that require longer sequences of integers: GCD, Gorilla, and OPERM5. These tests, along with the standard tests, were applied to 10 sequences of 100 million 32-bit integers. Here are the results:

RNG: Failed tests: cellular automaton 0 of 2690 gsl_rng_taus 0 of 2690 gsl_rng_gfsr4 0 of 2690 gsl_rng_mt19937 0 of 2690 gsl_rng_ranlxd1 5 of 2690

The results above show that the cellular automaton produces random sequences that are comparable in terms of statistical measurements of randomness to the GSL random number generators. In addition, the automaton is more than three times faster than the GSL generators. This shows that cellular automata can outperform standard random number generators without using parallel processing.

Although the Diehard test results are a strong indication of randomness, it remains to be proved that the cellular automaton has a period of adequate length. Proofs regarding the period and other characteristics of cellular automata have been demonstrated in previous research; see for example [4] and [5]. Proof and analysis of this particular automaton's characteristics is a task for future research.

Speed results:

cellular automatonGSL generators

Speed results and parsed Diehard results:

cellular automatonGSL generators

test code for cellular automaton: ca-test.c

test code for GNU Scientific Library: gsl-test.c

python script for parsing Diehard results file: parse-diehard.py

This project was supported by a graduate research fellowship from the School of Graduate Studies at Southern Connecticut State University.

I would like to thank my adviser, Dr. Hrvoje Podnar, and Dean Sandra Holley of the Graduate School, and my wife, Yi-Kyong Chung, for their assistance and support.

[1] *Random Number Generator Performance*. (n.d.). Retrieved October 3, 2006, from
http://www.gnu.org/software/gsl/manual/html_node/Random-Number-Generator-Performance.html.

[2] Phillips, M. K. (2006). *Top Secret Crypto Gold and the Diehard Battery of Tests of Randomness.*
Retrieved September 17, 2006 from http://www.topsecretcrypto.com/DieHard.htm.

[3] Intel Platform Security Division (n.d.). *The Intel Random Number Generator.*
Retrieved September 18, 2006 from http://citeseer.ist.psu.edu/435839.html.

[4] Matsumoto, M. (1998). Simple Cellular Automata as Pseudorandom m-Sequence Generators
for Built-In Self-Test. *ACM Transactions on Modeling and Computer Simulation*, 8(1), 31-42.

[5] Nandi, S. & Chaudhuri, P. (1996). Analysis of Periodic and Intermediate Boundary
90/150 Cellular Automata. *IEEE Transactions on Computers*, 45(1), 1-11.

*Last modified November 26, 2006*