1

我需要[LB,UB]在 C++ 的区间内从整数的均匀分布中随机抽样。为此，我从一个“好”的 RN 生成器（来自 Numerical Recipes 3rd ed.）开始，它均匀地随机采样 64 位整数；让我们称之为int64()。

使用 mod 运算符，我可以通过以下方式从整数中采样[LB,UB]：

LB+int64()%(UB-LB+1);

使用 mod 运算符的唯一问题是整数除法的速度很慢。所以，我然后尝试了这里建议的方法，即：

LB + (int64()&(UB-LB))

按位 & 方法的速度大约是 3 倍。这对我来说是巨大的，因为我在 C++ 中的一个模拟需要随机采样大约 2000 万个整数。

但是有1个大问题。当我分析使用按位 & 方法采样的整数时，它们在区间上看起来并不均匀分布[LB,UB]。整数确实是从 中采样的[LB,UB]，但仅从该范围内的偶数中采样。例如，这是使用按位 & 方法从 [20,50] 采样的 5000 个整数的直方图： 使用按位 & 方法采样的整数直方图

相比之下，使用 mod 运算符方法时类似的直方图看起来像这样，当然效果很好： 在此处输入图像描述

我的按位 & 方法有什么问题？有没有办法修改它，以便在定义的间隔内对偶数和奇数进行采样？

4

3 回答 3

2

位运算&符查看其操作数的每一对对应位，仅使用这两个位执行运算，and并将结果放入结果的对应位。

因此，如果 的最后一位UB-LB为 0，则结​​果的最后一位为0。也就是说，如果UB-LB是偶数，那么每个输出都是偶数。

&不适合目的，除非是 2的UB-LB+1幂。如果你想找到一个模数，那么就没有通用的捷径：编译器已经实现%了它知道的最快方法。

请注意，我说没有通用快捷方式。对于在编译时已知的特定值UB-LB，可以有更快的方法。而且，如果您可以以某种方式安排UB并LB获得编译器可以在编译时计算的值，那么它将在您编写时使用它们%。

顺便说一句， using%实际上不会在该范围内产生均匀分布的整数，除非该范围的大小是 2 的幂。否则一定会有轻微的偏向于某些值，因为您的int64()函数的范围不能在所需范围内平均分配。可能是偏差太小而无法特别影响您的模拟，但糟糕的随机数生成器过去破坏了随机模拟，并且会再次这样做。

如果您希望在任意范围内获得均匀的随机数分布，请使用std::uniform_int_distributionC++11 或 Boost 中的同名类。

于 2013-09-07T15:54:28.500 回答
2

如果范围差 ( UB-LB) 为 2 n -1，则此方法效果很好，但如果例如 2 n ，则效果不佳。

于 2013-09-07T15:44:24.000 回答
1

仅当区间的大小是 2 的幂时，两者才等价。一般来说 y%x 和 y&(x-1) 是不一样的。

例如，x%5 产生从 0 到 4 的数字（或到 -4，对于负 x），但 x&4 产生 0 或 4，从不产生 1、2 或 3，因为按位运算符的工作方式......

于 2013-09-07T15:42:40.163 回答