This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Haramoto, H. Articles by L'Ecuyer, P. Search for Related Content

Efficient Jump Ahead for ₂-Linear Random Number Generators

Department of Mathematics, Hiroshima University, Higashi-Hiroshima, Hiroshima 739-8526, Japan
Department of Mathematics, Hiroshima University, Higashi-Hiroshima, Hiroshima 739-8526, Japan
Department of Mathematical Sciences, Yamagata University, Yamagata 990-8560, Japan
Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, Montréal, Québec H3C 3J7, Canada
Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, Montréal, Québec H3C 3J7, Canada
haramoto{at}hiroshima-u.ac.jp
m-mat{at}math.sci.hiroshima-u.ac.jp
nisimura{at}sci.kj.yamagata-u.ac.jp
panneton{at}iro.umontreal.ca
lecuyer{at}iro.umontreal.ca

The fastest long-period random number generators currently available are based on linear recurrences modulo 2. So far, software that provides multiple disjoint streams and substreams has not been available for these generators because of the lack of efficient jump-ahead facilities. In principle, it suffices to multiply the state (a k-bit vector) by an appropriate k x k binary matrix to find the new state far ahead in the sequence. However, when k is large (e.g., for a generator such as the popular Mersenne twister, for which k = 19,937), this matrix-vector multiplication is slow, and a large amount of memory is required to store the k x k matrix. In this paper, we provide a faster algorithm to jump ahead by a large number of steps in a linear recurrence modulo 2. The method uses much less than the k² bits of memory required by the matrix method. It is based on polynomial calculus modulo the characteristic polynomial of the recurrence, and uses a sliding window algorithm for the multiplication.

Key words: simulation; random number generation; jumping ahead; multiple streams
History: accepted June 2007.