Efficient Jump Ahead for 𝔽2-Linear Random Number Generators

Efficient Jump Ahead for 𝔽2-Linear Random Number Generators

0.00 Avg rating0 Votes
Article ID: iaor200952622
Country: United States
Volume: 20
Issue: 3
Start Page Number: 385
End Page Number: 390
Publication Date: Jun 2008
Journal: INFORMS Journal On Computing
Authors: , , , ,
Keywords: simulation
Abstract:

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 × 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 × 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 k2 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.

Reviews

Required fields are marked *. Your email address will not be published.