Information Technology Reference
In-Depth Information
cases, this must be done thousands of times (or more) in a simulation, so we
need an ecient algorithm for this jump ahead. Unfortunately, for huge-period
generators such as the Mersenne twister and the WELL [4,5], for example, e-
cient jump ahead is dicult. For this reason, most current implementations use
a base generator whose state space is not so large (e.g., 200 bits or so), and this
limits the period length.
When the PRNG is based on a linear recurrence, a simple way to jump ahead is
to express the recurrence in matrix form, precompute and store the
J
-th power of
the relevant matrix, and jump ahead via a simple matrix-vector multiplication.
But for large-period generators, this method requires an excessive amount of
memory and is much too slow. Haramoto et al. [6] introduced a reasonably fast
jumping-ahead algorithm based on a sliding-window method. One drawback of
this method, however, is that it requires the storage of a large precomputed
table, at least in its fastest version.
The new method proposed in this paper is based on a representation of the
linear recurrence in a space of formal series, where jumping ahead corresponds
to multiplying the series by a polynomial. It requires much less memory than the
previous one, and is competitive in terms of speed. Under a certain condition on
the output function, the speed is actually
O
(
k
log
3
2
)
O
(
k
1
.
59
)fora
k
-bit state
space, compared with
O
(
k
2
) for the previous method. For the Mersenne twister
with period length 2
19937
≈
1, this condition is satisfied and the new method
turns out to be faster, according to our experiments.
The remainder is organized as follows. In Section 2, we define the setting in
which these jumping-ahead methods are applied, and we briefly summarize the
previously proposed techniques. The new method is explained in Section 3. Its
application to the Mersenne twister is discussed in Section 5. Section 6 reports
timing experiments.
−
2 Setting and Summary of Existing Methods
Many practical generators used for simulation are based on linear recurrences,
because important properties such as the period and the high-dimensional distri-
bution can then be analyzed easily by linear algebra techniques. For notational
simplicity, our description in this paper is in the setting of a linear recurrence in
a field of characteristic 2, i.e., we assume that the base field is the two-element
field
F
2
. However, the proposed method is valid for any finite field.
We consider a PRNG with state space
S
:=
2
, for some integer
k>
0, and
F
(state) transition function
f
:
S
F
2
.Thus,
f
can be identified
with its representation matrix
F
, a binary matrix of size
k
→
S
, linear over
S
is then a
k
-dimensional column vector. For a given initial state
s
0
,thestate
evolves according to the recurrence
×
k
, and a state
s
∈
s
m
+1
:=
f
(
s
m
)=
Fs
m
,
m
=0
,
1
,
2
,....
(1)
An output function
o
:
S
O
is specified, where
O
is the set of output symbols,
and
o
(
s
) is the output when we are in state
s
. Thus, the generator produces a
→
