Efficient jump ahead for F2-linear random number generators
Efficient jump ahead for F2-linear random number generators
复制标题
DOI：
10.1287/ijoc.1070.0251
复制
发表时间：
2008-06-01
影响因子：
2.1
通讯作者：
L'Ecuyer, Pierre
中科院分区：
文献类型：
--
作者：
Haramoto, Hiroshi;Matsumoto, Makoto;L'Ecuyer, Pierre
目前可用的最快的长周期随机数生成器基于模 2 的线性递推。到目前为止，由于缺乏有效的跳转设施，提供多个不相交流和子流的软件尚未可用于这些生成器。原则上，将状态（k 位向量）乘以适当的 k x k 二进制矩阵就足以找到序列中最前面的新状态。然而，当 k 很大时（例如，对于诸如流行的梅森扭曲器之类的生成器，其中 k = 19, 937），这种矩阵向量乘法很慢，并且需要大量内存来存储 k x k 矩阵。在本文中，我们提供了一种更快的算法，可以在模 2 的线性递推中向前跳转大量步骤。该方法使用的内存远少于矩阵方法所需的 k(2) 位内存。它基于多项式微积分对递推的特征多项式取模，并使用滑动窗口算法进行乘法。
T he 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(2) 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.