Information Technology Reference
In-Depth Information
A Fast Jump Ahead Algorithm for Linear
Recurrences in a Polynomial Space
Hiroshi Haramoto 1 , Makoto Matsumoto 1 , and Pierre L'Ecuyer 2
1 Dept. of Math., Hiroshima University, Hiroshima 739-8526 Japan
m-mat@math.sci.hiroshima-u.ac.jp
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/eindex.html
2 Departement d'Informatique et de Recherche Operationnelle,
Universit´edeMontreal, Montreal, Canada
lecuyer@iro.umontreal.ca
http://www.iro.umontreal.ca/~lecuyer
Abstract. Linear recurring sequences with very large periods are widely
used as the basic building block of pseudorandom number generators. In
many simulation applications, multiple streams of random numbers are
needed, and these multiple streams are normally provided by jumping
ahead in the sequence to obtain starting points that are far apart. For
maximal-period generators having a large state space, this jumping ahead
can be costly in both time and memory usage. We propose a new jump
ahead method for this kind of situation. It requires much less memory
than the fastest algorithms proposed earlier, while being approximately
as fast (or faster) for generators with a large state space such as the
Mersenne twister.
1
Introduction
Pseudorandom number generators (PRNGs) are widely used in many scientific
areas, such as simulation, statistics, and cryptography. Generating multiple dis-
joint streams of pseudorandom number sequences is important for the smooth
implementation of variance-reduction techniques on a single processor (see [1,2,3]
for illustrative examples), as well as in conjunction with parallel computing. Gen-
erators with multiple streams and substreams have been already adopted, or are
in the process of being adopted, in leading edge simulation software tools such as
Arena, Automod, MATLAB, SAS, Simul8, SSJ, Witness, and ns2, for example.
The substreams are normally obtained by splitting the sequence of a large-period
generator into long disjoint subsequences whose starting points are equidistant
in the original sequence, say J steps apart. To obtain the initial state (or start-
ing point) of a new substream, we must jump ahead by J steps in the original
sequence from the initial state of the most recently created substream. In many
 
Search WWH ::




Custom Search