10

假设我们有一个二进制随机数生成器,int r();它将返回 0 或 1,概率均为 0.5。

我查看了 Boost.Random,它们会生成 32 位并执行类似这样的操作(伪代码):

x = double(rand_int32());
return min + x / (2^32) * (max - min);

我对此有一些严重的怀疑。double 有 53 位尾数,32 位永远无法正确生成完全随机的尾数,除此之外还有舍入误差等。

假设 IEEE754 ,创建均匀分布floatdouble半开范围的快速方法是什么?[min, max)这里的重点在于分布的正确性,而不是速度。

为了正确定义正确,正确的分布将等于如果我们采用无限精确的均匀分布随机数生成器,并且对于每个数字,我们将四舍五入到最接近的 IEEE754 表示,如果该表示仍在[min, max),否则该数字将不计入分布。

PS:我也会对开放范围的正确解决方案感兴趣。

4

4 回答 4

4

AFAIK,正确(并且可能也是最快)的方法是首先创建一个 64 位无符号整数,其中 52 个小数位是随机位,指数是 1023,如果类型被双打成(IEEE 754)双精度将是一个统一的分布在 [1.0, 2.0) 范围内的随机值。所以最后一步是从中减去 1.0,从而得到在 [0.0, 1.0) 范围内均匀分布的随机双精度值。

在伪代码中:

rndDouble = bitCastUInt64ToDouble(1023 << 52 | rndUInt64 & 0xffffffffffff) - 1.0

这里提到了这个方法:http: //xoroshiro.di.unimi.it (参见“在单位区间内生成均匀双精度数”)

编辑:推荐的方法已更改为: (x >> 11) * (1. / (UINT64_C(1) << 53))

有关详细信息,请参阅上面的链接。

于 2016-07-17T21:02:41.787 回答
3

这是一种不追求效率的正确方法。

我们从一个 bignum 类开始,然后是上述 bignum 的合理包装器。

我们产生了一个“比”我们的范围“足够大”的[min, max)范围,因此我们的四舍五入smaller_minbigger_max产生超出该范围的浮点值,在我们基于大数的理性中。

现在我们将范围完全细分为中间的两部分(我们可以这样做,因为我们有一个合理的 bignum 系统)。我们随机选择两个部分之一。

如果在四舍五入后,所选范围的顶部和底部将 (A) 超出[min, max)(在同一侧,请注意!)您拒绝并从头开始。

如果 (B) 范围的顶部和底部舍入相同double(或者float如果您返回一个浮点数),那么您就完成了,并且您返回这个值。

否则(C)你在这个新的、更小的范围上递归(细分、随机选择、测试)。

无法保证此过程会停止,因为您可以不断深入到两个舍入doubles 之间的“边缘”,或者您可以不断选择[min, max)范围之外的值。然而,这种情况发生的概率是(从不停止)为零(假设一个好的随机数生成器,并且 a[min, max)的大小不为零)。

这也适用于(min, max),甚至在圆润的足够胖的康托集中选择一个数字。只要四舍五入到正确浮点值的有效实数范围的度量不为零,并且该范围具有紧凑的支持,则可以运行此过程并且具有 100% 的终止概率,但没有硬上限可以制作所需的时间。

于 2013-10-03T20:51:37.687 回答
2

这里的问题是,在 IEEE754 中,可能表示的双精度数分布不均。也就是说,如果我们有一个生成实数的生成器,比如在 (0,1) 中,然后映射到 IEEE754 可表示数,则结果将不会均匀分布。

因此,我们必须定义“平均分配”。也就是说,假设每个 IEEE754 数字只是代表位于 IEEE754 舍入定义的区间内的概率,则首先生成等分布“数字”和向 IEEE754 舍入的过程将(根据定义)生成“ IEEE754 号码的均匀分布”。

因此,我相信只要我们选择足够高的准确度,上面的公式就会变得任意接近这样的分布。如果我们将问题限制为在 [0,1) 中找到一个数字,这意味着限制为一组非正规化的 IEEE 754 数字,它们是一对一的 53 位整数。因此,通过 53 位二进制随机数生成器仅生成尾数应该是快速且正确的。

IEEE 754 算术始终是“以无限精度进行算术然后四舍五入”,即表示 a b 的 IEEE754 数字是最接近 a b 的数字(换句话说,您可以认为 a*b 以无限精度计算,然后四舍五入到关闭 IEEE754 号)。因此,我相信 min + (max-min) * x,其中 x 是一个去规范化的数字,是一种可行的方法。

(注意:从我的评论中可以清楚地看出,我首先不知道你在哪里指向最小值和最大值不同于 0,1 的情况。非规范化数字具有它们均匀分布的属性。因此你得到 equi 分布将 53 位映射到尾数。接下来您可以使用浮点运算,因为它在机器精度上是正确的。如果您使用反向映射,您将恢复均匀分布。

有关此问题的另一方面,请参阅此问题:Scaling Int uniform random range into Double one

于 2013-10-03T19:51:45.293 回答
1

std::uniform_real_distribution.

STL 在今年的 Going Native 会议上有一个非常好的演讲,解释了为什么应该尽可能使用标准发行版。简而言之,手工编写的代码往往质量差得可笑(想想std::rand() % 100),或者有更微妙的一致性缺陷,例如(std::rand() * 1.0 / RAND_MAX) * 99在演讲中给出的示例,并且是问题中发布的代码的一个特例。

编辑:我查看了 libstdc++ 的实现std::uniform_real_distribution,这就是我发现的:

该实现通过对 range 中生成的某个数字[dist_min, dist_max)使用简单的线性变换来生成 range 中的数字[0, 1)。它使用 生成此源编号std::generate_canonical我可以在此处找到其实现(在文件末尾)。确定分布范围的std::generate_canonical次数(表示为k),表示为整数,此处表示为*,将适合目标类型的尾数。然后它所做的基本上是为尾数的每个大小的段生成一个数字,并使用算术相应地填充每个段。结果值的公式可以表示为r[0, r)r

Σ(i=0, k-1, X/(r^i))

其中X是 中的随机变量[0, r)。范围的每个除法相当于用于表示它的位数(即log2(r))的移位,因此填充相应的尾数段。这样,使用了目标类型的全部精度,并且由于结果的范围是[0, 1),因此指数保持为0**(模偏差),并且当您开始弄乱时,您不会遇到一致性问题指数。

我不相信这种方法在密码学上是安全的(而且我怀疑在计算 的大小时可能会出现错误r),但我想它在一致性方面比你的 Boost 实现更可靠张贴,绝对比摆弄std::rand.

可能值得注意的是,Boost 代码实际上是该算法的退化情况,其中k = 1,这意味着如果输入范围需要至少 23 位来表示其大小(IEE 754 单精度)或至少 52 位,则它是等效的(双精度)。这意味着最小范围分别为~840 万或~4.5e15。根据这些信息,我认为如果您使用二进制生成器,Boost 实现不会减少它。

在简要了解libc++ 的实现之后,看起来它们使用的是相同的算法,但实现方式略有不同。

(*)r实际上是输入的范围加一。这允许使用maxurng 的值作为有效输入。

(**) 严格来说,编码的指数不是0,因为 IEEE 754 在有效数字的基数之前编码了一个隐含的前导 1。然而,从概念上讲,这与该算法无关。

于 2013-10-03T22:14:11.633 回答