在 64 位浮点随机生成器上测试随机性(均匀分布)

机器算法验证 卡方检验 随机生成 均匀分布
2022-04-19 01:48:25

我们有一个随机数生成器,它应该均匀地生成 64 位浮点数。

我们想测试它是否是一个好的均匀随机。

我不是在问测试它的一般方法,因为它在这里被问到https://stackoverflow.com/questions/22916519/test-the-randomness-of-a-black-box-that-outputs-random-64-位浮点数

据我了解,测试的第一步是以某种方式将整个范围划分为相同大小的箱,然后我们继续生成并查看落入每个箱的“球”的数量。

我的问题是关于这第一步。

我应该如何拆分整个 64 位浮点数范围?

范围介于-1.79769313486231571e+308和之间,1.79769313486231571e+308而且非常大。

我的想法是利用64 位我可以像这样设计相同大小的垃圾箱吗:

  1. 每个浮点数都有 64 位,所以我们有 64 个 bin。
  2. 对于生成的每个浮点数,我们读取所有这些位,如果一个位是 1,那么我们将相应的 bin 的编号增加 1
  3. 经过 N 次采样后,每个 bin 的预期数量应为N/2
  4. 然后我们进行皮尔逊卡方检验等。
2个回答

就目前而言,这不是测试浮点数是否均匀分布的好方法。Aksakal一样,我想知道浮点表示的指数部分的位是否会均匀分布。答案是它们不是均匀分布的,因为大指数的数字比小指数的数字多得多。

我写了一个小测试程序来证实这一点。它生成均匀分布的随机浮点数,并作为控件生成个随机整数。(生成 64 位浮点数时存在各种问题,请参见此处,并且 32 位似乎足以用于演示目的。)N=1 millionN

首先,控制案例。正如您所建议的那样,整数位箱的图是每个箱N/2在此处输入图像描述

现在是浮点数。排序数字的图是一条直线,表明它们将通过Kolmogorov-Smirnov一致性检验。 在此处输入图像描述

但是这些垃圾箱绝对不是统一的。 在此处输入图像描述

如果您仅将箱 1 到 23 与箱 32 一起绘制,您确实会得到箱,但箱 24 到 31 显示出明显的增加模式。这些位与 32 位浮点数中的指数位精确对应。IEEE单精度浮点定义规定N/2

  • 最低有效 23 位用于尾数
  • 接下来的 8 位是指数
  • 最重要的位是符号

另一种看待这一点的方法是考虑一个更简单的例子。考虑在 0 和之间生成以 10 为底的数字,指数以 10 为底。0 到 1 之间的数字的指数为 0。1 到 10 之间的数字的指数为 1,10 到 100 之间的数字的指数为 2,...,的数字为指数7. 数字是范围的并且在二进制中它们的指数范围从 001 到 111,所以你会期望最高有效位出现 99.9% 的时间,而不是 50% 的时间。107106107104107(107104)/107=99.9%

可以小心翼翼地使用这样的方法来获得浮点数二进制指数中每个 bin 的预期频率,并在测试中使用它,但 Kolmogorov-Smirnov 是理论上更好的方法,易于实施。然而,像这样的测试可能会在 Kolmogorov-Smirnov 可能不会的随机数生成的实现中发现分布偏差。例如,当我第一次尝试在 C++ 中生成 64 位双精度浮点随机数时,我忘记更改为64 位 Mersenne Twister 引擎排序后的数字给出了一条直线图,但您可以从比特箱的图中看到,64 位 Mersenne Twister 引擎优于 32 位引擎(如您所料)。χ2

在此处输入图像描述

(请注意,在这两种情况下,由于难以在整个范围内生成随机数,最后一位符号位为零。)

你看过NIST的用于加密应用程序的随机和伪随机数生成器的统计测试套件吗?

我认为这是开始分析的好地方。