Dynamics of complex systems lead many processes in real world to be assumed
stochastic and ambiguous (Bar-Yam, 1997). Due to this
motivation in recent decades, scientists has paid attention to computer based
random number generating in complex system simulations and attracted many researchers
to introduce and develop these methods (Ayanzadeh et al.,
2008; Moghaddas et al., 2008; Bar-Yam,
1997; Banks et al., 2004).
Lottery, computer games, cryptography, calculation with Monte Carlo method,
computer simulations, operational research and most of intelligent optimization
algorithms such as genetic algorithm, particle swarm optimization, tabu search
and other Meta-heuristics are some applications of random number generators
(Jang et al., 1997; Banks et
al., 2004; Viega, 2003; Kalos,
2007). Random numbers are generally classified to 3 categories as below:
Truly random numbers: In this category, all numbers have equal probability
to be generated. This class is not periodic and the numbers dont follow any
pattern. In addition, truly random numbers are not generated by specific algorithm
and prediction of next element of sequence is not possible. Indeed there is
no correlation among these kinds of random numbers (Kohlbrenner
and Gaj, 2004).
Pseudo random numbers: Pseudo random numbers are generated by specific
algorithms and it is possible to predict some subsequences by considering generated
trajectory. To start the algorithm it is needed that some of parameters be initialized.
One of the most obvious problems about this category is existence of periods
and specific patterns in sequences (Viega, 2003).
Quasi random numbers: In fact quasi random numbers are sequences of
nonrandom numbers which are shuffled to be seemed random. Thus these types of
random numbers are so suitable for calculation with Monte Carlo method (Lecuyer,
2003; Chen and Markel, 2005).
It is clear that random number generators must be adaptable with various statistical distributions due to application (e.g., uniform, normal, exponential, Poisson, Erlang). Uniform random numbers are applied in vast variety of applications. According to outstanding role of uniform random numbers in computer simulations, represented approach in this study is proposed to satisfy these requirements.
High period, low computational space and time order for random number generation
and low correlation among random numbers are some of important factors which
determine the performance of a typical random number generator (Ayanzadeh
et al., 2008).
RANDOM NUMBER GENERATORS
In 1927, Tippet designed table of forty thousand random numbers to use in
various applications. One hundred thousand of random numbers were generated
in a table designed by Kendall in 1939. Smith followed Kendalls study and designed
mechanical random generator device in 1955. The exciting point about these tables
is that they were filled without any specific algorithm. In 1951 Neumann proposed
a computational method (however this method had low performance). In recent
decades several algorithms were developed for random number generation as below
(Ayanzadeh et al, 2008; Moghaddas
et al., 2008; Hortensius et al., 1989).
Linear congruential generators: Linear Congruential methods use specific
algorithm to generate random numbers. These algorithms are iterative and initial
state is needed to start the algorithm. A sample of these algorithms is indicated
in Eq. 1:
Xn = (aXn-1 +c )
where, Xn-1 is the generated random number in previous iteration
a and c are constant coefficients, m is congruential module (one unit more than
maximum allowed random number) and Xn is the output of algorithm.
In this method generated random number extremely depends on its previous value.
Maximum period of m this algorithm is m (Chen and Merkel,
Multiple recursive generators: Multiple recursive generators are like linear congruential generator, but this method use k random numbers from previous iterations. A multiple recursive generator is indicated in Eq. 2.
In Eq. 2, ai are constant coefficients of algorithm,
Xn-iis output of algorithm in (n-i)th iteration and m
is congruential module (one unit more than maximum allowed random number). The
advantage of this method is that maximum period of algorithm is 2m
which is much more than period of Linear congruential method (Chen
and Merkel, 2005).
Lagged fibonacci generators: Lagged Fibonacci generators are a special case of famous Fibonacci sequence which use two outputs of previous iterations. Eq. 3 indicates the general form of this method.
where, m, Xn-k and Xn-1 are same with these parameters
in multiple recursive generator method. k and l are the indexes of numbers which
were generated in previous iterations. Performance of algorithm depends on selection
of these values (Chen and Merkel, 2005).
Summation operator in Eq. 3 can be changed by any other operator
(e.g., subtraction operator). Moreover it is possible to use binary logic operators
to generate random bits. In this case if the operator is exclusive or (XOR)
the method will be called transfer register generator thus the congruential
operator will be neglected from equation and Eq. 3 will be
changed to Eq. 4:
Output of Eq. 1 up to Eq. 3 will be random
numbers between zero and m.
Blum blum shub random generator: This generator was introduced by Blum
and his team but due to slow functionality of this method it was never used
in computer simulations. This method is widely used in cryptography. By using
this method, random numbers will be generated via Eq. 5:
where, m is congruential module and usually is considered as production of
two big prime numbers (Chen and Merkel, 2005).
Cellular Automata (CA) are discrete computational models that contain networks
of completely same cells which have interaction with together within a neighborhood
structure. Various neighborhood structures are proposed till now. Some of the
most popular models are: Neumann, Moore, Cole and Smith which are shown in Fig.
1. In Fig. 1, it is assumed that neighborhood radius equals
one (Ayanzadeh et al., 2008; Bar-Yam,
1997; Sarkar, 2000).
Cells state (value) is selected from a finite set. These values are changing
synchronously in iterations by using of some transition rules which are same
for all cells. Next states will be determined according to current values of
cells and current values of neighbors (Sarkar, 2000).
neighborhood structures in cellular automata|
Binary cellular automata are one of the most common simulation tools where
each cell can be stated as zero or one. Transition rules are determined by Boolean
algebra rules (AND, OR and NOT). Wolfram (1986) proposed
to use decimal value of bit sequence of next state to name the rules.
Some of the most useful Wolfram transition rules in linear binary cellular
automata are shown in Fig, 2 where first row is current states
of left neighbor, the cell and right neighbor, respectively. Next state of cell
is indicated in other rows by using of specified rules. Using transition rules
in Fig. 2 and starting from a random configuration leads to
generate pseudo random bits. Locality of rules leads to generate pseudo random
bits with desirable period (Wolfram, 1986).
TWO-LAYER CELLULAR AUTOMATA FOR RANDOM NUMBER GENERATING
Generating sequence of binary bits and combining these bits is one of the
most popular methods used in cellular automata based random number generators.
It is clear that quality of generated random numbers in such methods depends
on quality of sequence of random bits. Binary cellular automata will generate
high period pseudo random bits by using wolfram transition rules 30, 90, 105,
110 and 165 in isolated or hybrid manner.
Framing the sequence of generated random bits-base mapping-will cause to appearance of various patterns in final sequence of random numbers. Obviously appearance of patterns among sequences of random numbers means low quality of random number generator. It is possible to compensate this problem by using parallel cellular automata to some extent. However, range of generated random numbers can demand large number of needed bits. In this case using independent cellular automata per bit will extremely increment consumption of memory and time order.
Mismatching between range of random numbers before and after base mapping is
the other problem that will cause improper results. In binary numerical systems,
a binary number with length n envelopes range of zero up to 2 n-1.
Thus if it is impossible to map the desired range of random numbers to such
range, mapping the range will increment the chance of numbers of specific sub
range to be generated.
rules in binary CA|
layers CA for uniform random number generation|
For example five bits are needed to generate random numbers
in range [0, 20] but five bits envelope range of [0, 31].
The simplest way to handle this problem is to ignore random numbers bigger
than 20. However, this method may produce patterns and reduce the quality of
generated random numbers. The other approach to compensate this problem is using
of linear (or nonlinear) mapping. It is clear that if the length of origin range
is bigger than length of destination range, chance of random numbers to be generated
wont be the same. In such condition the uniformity will reduce.
Based on this issue, in this study a novel structure of cellular automata is proposed to be used as random number generator. Proposed model is constructed from two heterogeneous layers of cellular automata. Each layer contains a two dimensional cellular automata with same size.
Cells of first layer are binary and include zero or one bits. If the goal is to generate uniform random numbers in range [0, n] then the cells of second layer will include integer numbers between zero and n. structure of proposed model is shown in Fig. 3.
Each row of binary cellular automata-in first layer is assumed as independent linear binary cellular automata.
Thus each cell is adjacent with one right neighbor cell and one left neighbor cell. Associated values of cells of each row will be updated using one of the Wolfram transition rules 30, 90, 105, 110 or 165.
A novel neighborhood structure-named pseudo Neumann-is applied in next layer. In proposed model-like Moore standard neighborhood structure-eight neighbors of each cell are considered as adjacent. The difference between pseudo Neumann and Moore structure is that if cells with same positions from first layer equal one they will be active, otherwise they will be inactive. If the cells of first layer generate uniform random bits, the cells of second layer will activate/inactive with same probability. In this case about half of cells in neighborhood structure-about four cells like Neumann structure-will be active. Interaction between first and second layers of cellular automata leads pseudo Neumann neighborhood structure to be assumed as Neumann neighborhood structure with dynamic adjacency.
States of each cell in second layer will be updated by dividing summation of cell value and active neighbors values to n+1. Remainder of this division is the next value of cell. According to this rule, values of cells will be between zero and n. Initial configuration of automata must be uniform. In other words chance of integer numbers between 0 to n to be generated must be equal. Now each cell of second layer is a random integer with uniform distribution.
If lower bound of needed random numbers is not zero, it is possible to map the generated random numbers to desired range by using a simple linear mapping. For example if desired range of random numbers is [-100,100] then n will initialized with 200 and -100 will be added to output results.
SIMULATION AND EVALUATION OF PROPOSED MODEL
Here, simulation results of two-layer cellular automata in random number generation will be discussed. Each layer consists of a 1000x1000 cellular automata. States of cells in first layer are updated by using rule 30.
In the following, capability of binary cellular automata to produce random bits by using rule 30 will be discussed and second experiment will compare the uniformity of generated random numbers by proposed model with MATLAB.
Experiment 1: Objective of this experiment is evaluating capability
of cellular automata to generate random bits. To reach this purpose, simulation
of linear binary cellular automata with one hundred cells was implemented. In
this simulation neighborhood radius was one and rule 30 was used to change the
cell values 103 random bits were generated and total numbers of ones
which were appeared in sequence were computed. This simulation had been run
for one hundred times and statistical features such as average, standard deviation
and scattering length were extracted. Table 1 contains simulation
Obviously, Table 1 indicates that quality of generated random bits by using of cellular automata is very desirable and output random bits of automata follow the uniform distribution. Thus if rule 30 is used to update the values of first layer of proposed model, then cells of second layer will activate and inactive with approximately same probability.
Experiment 2: Purpose of this experiment is evaluating the uniformity of generated random numbers in proposed model. Thus, sequence of random numbers is generated by second layer of proposed model and integer random number generator of MATLAB. Then an experiment is implemented as below.
N = 104 random numbers in the range of [0,100]|
the generated numbers in c = 10 classes with equal sizes
the frequency of numbers in each class (fi)
After running these steps for one hundred times, average, standard deviation and scattering length of frequencies of classes are computed. Table 2 contains the experiment results. Histogram diagrams of calculated frequencies of two-layer cellular automata and MATLAB are shown in Fig. 4 and 5, respectively. Comparing Fig. 4 and 5 results that generated random numbers by two-layer cellular automata are more uniform than MATLAB.
diagram of classified generated random numbers by two-layer CA|
features of experiment 1|
diagram of classified generated random numbers by MATLAB|
In this study, two-layer cellular automata and pseudo Neumann neighborhood structure are introduced. Based on these novel concepts, an innovative approach to generate uniform random numbers is proposed. In this model, cells of automata which are responsible to generate random numbers contain integer values and this is against previous random number generating approaches which were based on generating random bits by using cellular automata. These cells are activated and inactivated by cells of a binary automaton in first layer. This condition leads cellular automata to obtain dynamic neighborhood structure. Simulation results of proposed method and comparing uniformity quality of this method with random number generator of MATLAB proved that two-layer cellular automata generate random numbers with more uniformity. High period, low computational space and time order and low correlation among random numbers are some advantages of proposed model. Also, the output of proposed model can be used as BCD random number. Main problem of this method is initial configuration which may cause Garden of Eden. Applying hybrid transition rules, neighborhood structures and hardware implementation can improve the performance of two-layer cellular automata model.