Fast Random Integer Generation in an Interval
Fast Random Integer Generation in an Interval
复制标题
DOI：
10.1145/3230636
复制
发表时间：
2019-02-01
影响因子：
0.9
通讯作者：
Lemire, Daniel
中科院分区：
文献类型：
--
作者：
Lemire, Daniel
在模拟、概率算法和统计测试中，我们经常在一个区间内生成随机整数（例如，[0,s]）。例如，区间内的随机整数对于费雪-叶茨随机洗牌是必不可少的。因此，诸如Java、Python、c++、Swift和Go等流行语言都将范围随机整数生成函数作为其运行时库的一部分。伪随机值通常使用线性同余生成器等算法以固定位数的字（例如32b， 64b）生成。我们需要在不引入统计偏差的情况下将这些随机单词转换为区间（[0,s）)内的随机整数的函数。Java等编程语言中的标准函数涉及整数除法。不幸的是，除法指令是相对昂贵的。我们回顾了一个从随机词源生成范围整数的无偏函数，该函数避免了高概率的整数除法。为了证明该方法的实用性，我们证明了该算法可以在x64处理器上乘以无偏随机洗牌的速度。我们提出的方法已被Go语言用于实现shuffle函数。
In simulations, probabilistic algorithms, and statistical tests, we often generate random integers in an interval (e.g., [0, s)). For example, random integers in an interval are essential to the Fisher-Yates random shuffle. Consequently, popular languages such as Java, Python, C++, Swift and Go include ranged random integer generation functions as part of their runtime libraries.Pseudo-random values are usually generated in words of a fixed number of bits (e.g., 32b, 64b) using algorithms such as a linear congruential generator. We need functions to convert such random words to random integers in an interval ([0, s)) without introducing statistical biases. The standard functions in programming languages such as Java involve integer divisions. Unfortunately, division instructions are relatively expensive. We review an unbiased function to generate ranged integers from a source of random words that avoids integer divisions with high probability. To establish the practical usefulness of the approach, we show that this algorithm can multiply the speed of unbiased random shuffling on x64 processors. Our proposed approach has been adopted by the Go language for its implementation of the shuffle function.