To implement the stochastic model mentioned in Section 3.1, uniformly distributed pseudorandom numbers are needed to accurately predict a new land-cover value for a cell based on the the transition probabilities. Unfortunately, most vendor-provided random number generators (RNGs) are not sufficient for such modeling [26,4]. ``Good'' random numbers should be uniformly distributed, statistically independent and reproducible [29,24]. Truly random numbers are not reproducible without storing them, so pseudorandom numbers are more suitable for simulations. Repeating a sequence of random numbers is desirable to debug simulations and two policies can be more accurately compared statistically if both use the same ``random'' sequence [4].
According to Knuth and others [17,4,29,26], a very standard technique for generating pseudorandom numbers is the use of linear congruential generators (LCG) which were first introduced by Lehmer in 1949 [18]. LCGs compute the ith integer in a pseudorandom sequence by the recursion found in Equation (3).
where multiplier a, increment c, and modulus m determine the
statistical quality of the generator. This generator meets many of
the criteria established for a ``good'' RNG including the fact that it
requires very little memory to implement. The problem with LCGs is
that their period is limited to m [29]. All
pseudorandom number generators suffer because the sequences they
generate are periodic, i.e., there exists an integer t such that
for all 
, where 
is the nth number in a
random sequence [24]. Without using costly
multiple-precision arithmetic, the cycle generated by LCGs is bounded
by the length of the machine word. Thus on a machine with 32-bit
integer arithmetic (31-bit with the sign bit), this means that a
maximum of 
2,147,483,647 numbers can be generated before
the sequence repeats itself. Two billion may seem sufficient for a
single simulation, but if the transitions for large maps with millions
of cells are to be calculated for many time steps and replicates, this
period could be exhausted.
Park and Miller propose that Lehmer's LCG with 
, c=0 and
, the Mersenne prime, be adopted as a minimal standard
random number generator because it has been exhaustively tested and
its characteristics are well understood [26].
Another revolutionary generator using a feedback shift register (FSR)
was introduced in 1965 by Tausworthe [32]. It could
generate arbitrarily long sequences of random numbers without the
multidimensional non-uniformities found in LCGs. The kth bit, 
,
of a random bit sequence is defined to be
and has its maximum possible cycle length if and only if the
polynomial 
is primitive over
GF[2].
However, Toothill et al. discovered
negative results running a statistical test of the Tausworthe FSR
method in 1971 [33]. Two years later Lewis and Payne
refined Tausworthe's generator to create a generalized FSR (GFSR)
[19]. Because this algorithm uses base two, the addition
operation without carry is the same as the binary exclusive OR
(XOR, denoted 
). Thus Equation (4) for integers
(groups of bits) is equivalent to
Using primitive trinomials, 
, p>q, Equation (5)
reduces to
This requires only one XOR operation and some address calculations for
each integer generated by the GFSR and therefore is just as fast, if
not faster than LCGs. It also requires careful initialization of the
vector before generating new random numbers. Kirkpatrick and Stoll
presented a specific implementation of the generator described by
Equation (6) (denoted R250) using q=103 and
p=250 [16]. In 1994 Carter created a C++ class library
[5] of R250 which uses Park and
Miller's minimal standard LCG to initialize the R250's bit vector.
LUCAS uses Carter's C++ implementation of R250 as its RNG. It
has an extremely long period (
) and is faster than an
LCG. It does require more memory, i.e., the storage of 250
integers, but this cost is negligible.
