Random number generation using a
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

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.

Results

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.

Speed:

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

Randomness:

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

Conclusion

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.

Files: source code and output

10 million integers:

Speed results:

cellular automaton
GSL generators

100 million integers:

Speed results and parsed Diehard results:

cellular automaton
GSL generators

Source code for cellular automaton and tests:

cellular automaton RNG: ca-rng.c
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

Diehard:

The source code for Diehard is available at the University of Hong Kong: http://www.csis.hku.hk/~diehard/

Acknowledgments

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.

References

[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

Valid XHTML 1.0 Transitional