我在随机数生成上的绝大多数帖子主要涉及各种生成方案的特性。 这可能出乎意料，但是随机算法的性能可能不取决于所选的生成方案，而是取决于其他因素。 在这篇文章（我
受Daniel Lemyr的一篇精彩
文章的启发 ）中，我们将研究导致随机数生成性能下降的主要原因，该性能通常超过PRN引擎的性能。
想象一下这种情况：
作为作业，Juan和Sasha在C ++中实现了相同的随机算法，该算法将在同一台大学计算机上运行，并具有一个数据集。 它们的代码几乎相同，只是在随机数的生成上有所不同。 Juan急于上音乐课，因此他只是选择了Mersenne旋风。 另一方面，Sasha花了一些额外的时间进行研究。 Sasha对几种最快的PRNG进行了基准测试，最近他从社交网络上获悉，并选择了最快的PRNG。 在会议上，Sasha不耐烦地吹牛，他问Juan：“您使用了哪种PRNG系统？”
“就我个人而言，我只是采用了Mersenne涡流-它是语言内置的，并且似乎运行得很好。”
“哈！”萨沙回答。 “我使用了
jsf32 。 它比古老而缓慢的梅森旋风要快得多！ 我的程序在3分15秒内运行！”
“嗯，还不错，但是我可以在不到一分钟的时间内做到这一点，”胡安耸耸肩说。 “那么，我必须去听音乐会。 你愿意和我一起去吗？
“不，”萨莎回答。 “我……呃……需要再次查看我的代码。”
这种尴尬的虚构情况
并不是特别虚构。 它基于实际结果。 如果您的随机算法的运行速度没有我们期望的快，并且瓶颈似乎是随机数生成，那么奇怪的是，问题可能出在随机数生成器上！
简介：实践中的随机数
大多数现代高质量随机数生成器都会创建填充有随机位的机器字，也就是说，它们通常会生成间隔为[0..2
32 ]或[0..2
64 ）的数字。 但是在许多使用情况下，用户需要一定时间间隔的数字-例如，掷骰子或选择随机纸牌，需要以较小的恒定间隔数字。 但是，从
混合和
储层采样到
随机二叉搜索树 ，许多算法都需要从其他间隔中获取数字。
方法
我们将研究许多不同的方法。 为了简化讨论，我们将在间隔[0 ..
k ）中生成数字，而不是在间隔[
i..j ]或[
i..j ]中生成数字。 有了这样的方案，我们可以，例如，通过设置
k =
j -
i ，在间隔[0 ..
k ）中生成一个数字，然后将其加
i来生成间隔[
i ..
j ）中的数字。
内置C ++工具
许多语言都有内置工具，可以在指定间隔内获取随机数。 例如，要从用52种卡以脚本语言（例如Perl和Python）从卡组中取出卡，我们可以分别编写
int(rand(52))和
random.randint(0,52) 。 [注意
CryptoPirate用户：
在我看来，这是一个错误，在python randint（a，b）中生成从a到b的数字，包括b。 并且由于卡片组中有52张卡片，并且第一张卡片为“ 0”，因此应该为random.randint（0,51） 。]在C ++中，我们可以
uniform_int_distribution相同的
uniform_int_distribution使用
uniform_int_distribution 。
用C ++代码实现这种方法很简单：
uint32_t bounded_rand(rng_t& rng, uint32_t range) { std::uniform_int_distribution<uint32_t> dist(0, range-1); return dist(rng); }
通常，内置工具使用以下描述的一种技术，但是大多数用户只是简单地使用这些工具，而没有考虑“幕后”的情况，而是认为这些工具设计正确并且非常有效。 在C ++中，内置工具更加复杂，因为它们应该能够与相当任意的生成引擎一起使用-生成值介于-3到17之间的生成器可能是非常有效的，并且可以与
std::uniform_int_distribution一起使用，以任意间隔创建数字，例如[0..1000）。 也就是说，对于大多数使用内置C ++工具的情况来说，它们太复杂了。
该分部的经典余数（偏斜）
让我们从过度简化的方法过渡到过于简单的方法。
当我学习编程时，我们使用余数运算符生成了间隔中的数字（例如，在52张牌中选择一张牌）。 为了获得区间[0..52）中的数字，我们编写了
rand() % 52 。
在C ++中，可以按以下方式实现此方法：
uint32_t bounded_rand(rng_t& rng, uint32_t range) { return rng() % range; }
尽管这种方法很简单，但它说明了在正确的间隔中获取数字通常是一项缓慢的任务的原因-它需要除法（以计算由
%运算符获得的余数）。 除法通常比其他算术运算至少慢一个数量级，因此单个算术运算要比快速PRNG执行的所有工作花费更长的时间。
但是除了低速外，它还
歪斜了 。 要了解为什么
rand() % 52返回不正确的数字，请假设
rand()在区间[0..2
32 rand()创建数字，并注意52不会将2
32完全除，而是将其除以82 595 524次48.也就是说，如果我们使用
rand() % 52 ，那么我们将有82 595 525种方法来选择牌组中的前48张牌，而只有82 595 524种方法来选择后四张牌。 换句话说，最后四张卡（可能是国王！）的歪斜为0.00000121％。 当我还是一个学生，写有关扔骰子或抽奖卡的作业时，通常没有人关心这种微小的变形，但是随着间隔的增加，变形呈线性增长。 对于32位PRNG，小于2
24的有限间隔的斜率小于0.5％，但大于2
31的斜率则为50％-一些数字返回的频率是其他数字的两倍。
在本文中，我们将主要考虑使用策略消除系统错误的技术，但是可能值得一提的是，对于64位PRNG，普通应用程序中的偏斜值可以忽略不计。
另一个问题可能是某些发生器的弱位较低。 例如，GPRS系列Xoroshiro +和Xoshiro +的低位不通过统计测试。 当我们执行
% 52 （因为52是偶数）时，我们将低阶位直接传递到输出。
乘以浮点数（偏斜）
另一种常用技术是使用PRNG，该PRNG会在间隔[0..1）中生成浮点数，然后将这些数字转换为所需的间隔。 这种方法在Perl中使用，
建议使用
int(rand(10))在区间[0..10）中生成整数，方法是生成浮点数，然后向下舍入。
在C ++中，这种方法是这样写的：
static uint32_t bounded_rand(rng_t& rng, uint32_t range) { double zeroone = 0x1.0p-32 * rng(); return range * zeroone; }
（请注意，
0x1.0p-32是2
-32的二进制浮点常数，我们将其用于将间隔[0..2
32 ]中的随机整数转换为单位间隔中的两倍； 相反，我们可以使用
ldexp(rng(), -32)进行这种转换，但是当我对该方法进行基准测试时，结果却慢得多。）
这种方法与经典除法方法一样偏斜，但是偏斜出现的方式有所不同。 例如，如果我们选择区间[0..52）中的数字，则数字0、13、26和39的出现频率将比其他数字少一次。
当泛化为64位时，此版本更加令人不快，因为它需要尾数至少为64位的浮点类型。 在具有Linux和macOS的x86机器上，我们可以使用
long double来利用具有64位尾数的精度更高的x86浮点数，但是
long double并不普遍移植到所有系统上-在某些系统中，
long double等于
double 。
有一个好的方面-这种方法比具有低位低位的PRNG的残留解决方案要快。
整数乘法（倾斜）
乘法方法可以适用于固定算法而不是浮点算法。 实际上，我们只是不断地乘以2
32 ，
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t x = rng(); uint64_t m = uint64_t(x) * uint64_t(range); return m >> 32; }
这个版本似乎需要64位算术运算，在x86处理器上，一个好的编译器会将这段代码编译为32位
mult指令（这给了我们两个32位输出值，其中一个是返回值）。 可以期望该版本很快，但是它的偏斜与浮点数相乘的方法完全一样。
掉落分割（无偏斜）
我们可以将浮点乘法方案修改为基于除法的方案。 代替乘以
x * range / 2**32我们计算
x / (2**32 / range) 。 由于我们正在使用整数算术，因此此版本中的舍入将以不同方式执行，有时会生成超出所需间隔的值。 如果我们丢弃这些值（例如，摆脱它们并生成新值），那么结果就是我们得到了一种没有失真的技术。
例如，在使用32位PRNG拔出卡的情况下，我们可以生成一个32位编号并将其除以2 32/52 = 82595524，以选择卡。 如果32位PRNG中的随机值小于52×82595524 = 2 32/32-48，则此技术有效。如果PRNR中的随机值是生成器区间上部的最后48个值之一，则需要丢弃它并寻找另一个。
我们针对该版本的代码使用了一种技巧，即不使用64位数学运算就将2
32除以
range 。 为了直接计算
2**32 / range我们需要表示数字2
32 ，该数字太大（乘以1！），不能表示为32位整数。 取而代之的是，我们考虑到对于无符号整数，一元取反运算
range计算出的正值为2
32 -
range ； 将该值除以
range ，得到的响应小于
2**32 / range 。
因此，用于使用除法和除法生成数字的C ++代码如下所示：
uint32_t bounded_rand(rng_t& rng, uint32_t range) {
当然，此方法需要两个基于除法的慢速运算，通常比其他算术运算要慢，因此您不应期望它很快。
除法的其余部分（双精度）-OpenBSD技术
我们也可以采用drop方法消除经典除法余数方法中的偏斜。 在使用纸牌的示例中，我们再次需要删除48个值。 在此版本中，我们（等效地）丢弃
前 48个值，而不是丢弃
后 48个值。
这是这种方法在C ++中的实现：
uint32_t bounded_rand(rng_t& rng, uint32_t range) {
该技术消除了偏斜，但是它需要两个耗时的除法运算以及每个输出值的其余部分（并且您可能需要一个内部生成器来创建多个数字）。 因此，应该预期该方法将比经典的偏斜方法慢大约两倍。
arc4random_uniform OpenBSD arc4random_uniform （在OS X和iOS上也使用）使用此策略。
除法的余数（单个）-不偏斜-Java方法
Java使用一种不同的方法在仅使用一个余数除法运算的间隔中生成数字，但极少数情况下会丢弃结果。 代码：
static uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t x, r; do { x = rng(); r = x % range; } while (x - r > (-range)); return r; }
要了解此选项为何起作用，您需要考虑一下。 与以前的版本不同，该版本基于残差，该残差通过从内部生成引擎中删除部分最低值来消除偏差，而该版本从引擎间隔的上部滤除值。
斜整数乘法-Lemira方法
就像我们从除法的其余部分中消除偏差一样，我们可以消除整数乘法技术中的偏差。 该技术是Lemyr发明的。
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t t = (-range) % range; do { uint32_t x = rng(); uint64_t m = uint64_t(x) * uint64_t(range); uint32_t l = uint32_t(m); } while (l < t); return m >> 32; }
放置位掩码（无歪斜）-Apple技术
在我们的最后一种方法中，除法和余数运算被完全消除。 取而代之的是，它使用简单的屏蔽操作来获得间隔[0..2
k ）中的随机数，其中
k是最小值，使得2
k大于该间隔。 如果该值对于我们的间隔而言太大，我们将其丢弃并尝试获取另一个。 代码如下所示：
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t mask = ~uint32_t(0); --range; mask >>= __builtin_clz(range|1); uint32_t x; do { x = rng() & mask; } while (x > range); return x; }
苹果公司（在macOS Sierra版本中）对
arc4random_uniform代码进行
了自己的修订时，采用了这种方法。
对标基本技术
现在，我们可以评估几种方法。 不幸的是，当我们担心单个部门的成本时，基准测试就变得不容易了。 没有基准可以考虑到影响应用领域的所有因素，并且不能保证您的应用的最佳选择肯定是我的最佳选择。
我们使用三个基准，并使用许多不同的PRNG进行测试。
基准大洗牌
可能最明显的基准是混合。 在此基准测试中，我们模拟执行大规模混合。 为了对大小为
N的数组进行排序
，我们必须在[0 ..
N ），[0 ..（
N -1）），...，[0..1）的间隔中生成数字。 在此基准测试中，我们将假设
N是最大可能数（对于
uint32_t它是2
32 -1）。 代码：
for (uint32_t i = 0xffffffff; i > 0; --i) { uint32_t bval = bounded_rand(rng, i); assert(bval < i); sum += bval; }
请注意，我们通过将每个数字加到
sum “使用”每个数字（这样它就不会被优化丢弃），但是我们不会执行任何混合操作来关注数字的生成。
对于测试64位生成，我们有一个类似的测试，但是执行与混合大小为2 64-1的数组相对应的测试是不切实际的（因为要完成这个更大的基准需要花费数千年的时间）。 取而代之的是，我们跨越了整个64位间隔，但是生成的输出值数量与32位测试中的数量相同。 代码：
for (uint32_t i = 0xffffffff; i > 0; --i) { uint64_t bound = (uint64_t(i)<<32) | i; uint64_t bval = bounded_rand(rng, bound ); assert(bval < bound); sum += bval; }
梅森涡旋结果
下面显示的结果证明了对于使用Mersenne涡旋并在32位代码（使用
libstdc++ std::mt19937 ）和类似的64位代码（使用
libstdc++ std:mt19937_64 ）进行测试时，我们测试的每种方法的基准性能） 结果是具有不同种子值的15次运行的几何平均值，然后对其进行归一化，以便经典除法余数方法具有单个运行时间。
似乎我们对性能有明确的答案-似乎您可以构建用于完善性能的技术，并询问自己
libstdc++开发人员在编写如此糟糕的32位数字实现时在考虑什么。 但是，与基准测试一样，情况比这些结果看上去要复杂得多。 首先，存在结果可能特定于梅森涡旋的风险，因此我们将扩展许多经过测试的PRNG。 其次，基准本身可能存在一个细微的问题。 让我们首先处理第一个问题。
不同PRNG的结果
我们将使用
arc4_rand32 ，
chacha8r ，
gjrand32 ，
jsf32 ，
mt19937 ，
pcg32 ，
pcg32_fast ，
sfc32 ，
splitmix32 ，
xoroshiro64+ ，
xorshift*64/32 64/
xoshiro128+ ，
xoshiro128+和
xoshiro128**和带有
gjrand64 64位
gjrand64来测试32位
arc4_rand32 jsf64 ，
mcg128 ，
mcg128_fast ，
mt19937_64 ，
pcg64 ，
pcg64_fast ，
sfc64 ，
splitmix64 ，
xoroshiro128+ ，
xorshift*128/64 xoshiro256+ /
xoshiro256* ，
xoshiro256+和
xoshiro256* 。 这些套件将为我们提供一些缓慢的PRN和许多非常快速的PRN。
结果如下：
我们可以看到Mersenne涡旋产生的关键差异。 更快的PRNG将平衡移向边界代码，因此不同方法之间的差异变得更加明显，尤其是在64位PRNR的情况下。 随着
libstc++实现
libstc++那么可怕。
结论
在此基准测试中，基于乘以偏差的方法在速度上是有优势的。 在许多情况下，相对于PRNG的大小，边界会很小，并且性能绝对至关重要。 在这种情况下，轻微的偏差不太可能产生明显的效果，但PRNG速度会有所提高。 一个这样的例子是带有随机参考点的Quicksort。 在偏斜方法中，位掩码技术看起来很有希望。
但是，在做出严肃的结论之前，我们需要指出该基准测试的巨大问题-大部分时间都花在非常高的边界上，这很可能会给较大的间隔过分重视。 因此，我们需要转到第二个基准。
基准小洗牌
, « » (). :
for (uint32_t j = 0; j < 0xffff; ++j) { for (uint32_t i = 0xffff; i > 0; --i) { uint32_t bval = bounded_rand(rng, i); assert(bval < i); sum += bval; } }
结论
, .
, ; , , .
for (uint32_t bit = 1; bit != 0; bit <<= 1) { for (uint32_t i = 0; i < 0x1000000; ++i) { uint32_t bound = bit | (i & (bit - 1)); uint32_t bval = bounded_rand(rng, bound); assert(bval < bound); sum += bval; } }
结论
. , , , , .
, , .
, - , . , .
, :
uint32_t bounded_rand(rng_t& rng, uint32_t range) {
range ,
. , , .
:
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t r = rng(); if (r < range) { uint32_t t = (-range) % range; while (r < t) r = rng(); } return r % range; }
« Mod » (. ), « ». , ( ).
Large-Shuffle
64- ( mod ), 32- . , .
Small-Shuffle
, small-shuffle , . . (OpenBSD) (Java).
.
, : .
a % b , ,
a < b a , .
a/2 < b ,
a - b . ,
a %= b;
if (a >= b) { a -= b; if (a >= b) a %= b; }
, .
Large-Shuffle
large-shuffle. 64- , . ( OpenBSD) .
- , .
Small-Shuffle
small-shuffle, , . , .
.
:
, . .
32-
32- , , 32- :
, ,
pcg32_fast — Xoroshiro ( ). , - — . , 5%, , «».
64-
64- , , 32- . , 32- , 64- , 32- .
,
mcg128_fast , 5%, .
pcg64 pcg64_fast mcg128_fast , 128- (, LCG) 128- (, MCG). , ,
pcg64 20% 64- .
, , 64- , 64- , 32-.
结论
, (, 32- ) 45%. 66%; , .
( ) — ( ). :
uint32_t bounded_rand(rng_t& rng, uint32_t range) { uint32_t x = rng(); uint64_t m = uint64_t(x) * uint64_t(range); uint32_t l = uint32_t(m); if (l < range) { uint32_t t = -range; if (t >= range) { t -= range; if (t >= range) t %= range; } while (l < t) { x = rng(); m = uint64_t(x) * uint64_t(range); l = uint32_t(m); } } return m >> 32; }
, .
:
GitHub . 23
bounded_rand 26 (13 32- 13 64-), (GCC 8 LLVM 6), 26 * 23 * 2 = 1196 , 15 seed, 1196 * 15 = 17 940 , . 48- Xeon E7-4830v3 2,1 . .
. ,
jsf32.STD-libc++ , —
mt19937.BIASED_FP_MULT_SCALE . 3, 69,6% . .