在对数空间中均匀生成随机整数

Question

在对数空间中均匀生成随机整数

4

我希望生成在“对数空间”中均匀分布的随机整数。也就是说，这些值的对数将是均匀分布的。

一个正常的均匀分布无符号整数有75%的数量级在10亿以上，而像99.98%在100万以上，所以小值的数量较少。来自对数空间的均匀值将在4-8范围内具有相同数量的值，例如256-512。

现在先忽略负值，我能想到的一种方法是：

Random r = new Random();
return (int)Math.pow(2, r.nextDouble() * 31);

那会生成一个31位的对数均匀分布。不过速度不会很快，其中有一个pow（）操作，并且引入浮点值以生成整数有点不好。此外，Random.nextDouble（）的很多范围都被丢失了。我不确定此代码甚至能否生成所有2 ^ 31-1个正整数值。

欢迎更好的解决方案。

下面有两个类似的解决方案，它们都涉及用随机位填充整数，然后向右移动随机位数。大概是这样的：

int number = rand.nextInt(Integer.MAX_VALUE) >> rand.nextInt(Integer.SIZE);

这里有两种偏差：

阶梯式偏差

这会产生一种类似阶梯状对数分布的值，而不是平滑的对数分布。特别地，在 [0,31] 之间随机移动，意味着存在 31 种等概率的整数“大小”，并且该范围内的每个值都是等概率的。由于在区间 N 中有 2^N 种值，因此一个区间中的值是下一个区间中的值的两倍 - 因此在区间之间得到对数行为，但区间本身是平坦的。

我不知道有什么简单的方法可以消除这种偏差。

最高位偏差

第二种形式的偏差发生是因为 MSB 不总是 1（例如，即使移位量为 10，也不一定会产生一个 31-10=21 位值，存在额外的扭曲。实际上，范围重叠。值 1 不仅出现在移位量为 30 时（p(1)=.5），还出现在移位量为 29（p(1)=0.25）、28（p(1)=.125）等情况下。这种影响对较小的值没有影响（即，如果只考虑移位量为 30 和 29，那么 1 看起来比预测值 2 倍更有可能出现，而不是 3 倍），但一旦考虑到更多的值时它就会收敛。然而，对于较大的值，这种影响并没有消失，这就是为什么在 @sprinter 的答案中看到 20:32207 bucket 比其他 bucket 小的原因。

我认为可以通过强制将最高位设置为零来轻松消除这种偏差，因此可以编写如下代码：

(r.nextInt(0x40000000) | 0x40000000) >> r.nextInt(31)

这里有几个其他微调 - 它使用了 2^30 作为 rand 的最大值，这样更快（在 nextInt(int) 代码中对 2 的幂进行特殊处理），因为我们永远不希望第二位从 MSB 被设置（我们强制将其设置为 1）。这还消除了一种微小的额外偏差来源，即 Integer.MAX_VALUE 永远无法生成，因此一个值从完整表示中缺失。

它通过 [0,31) 位移，所以你永远不会得到零，如果你也想得到零，请将其改为 [0,32) 位移，这样你就可以得到与 1 相等频率的零（严格来说不再是对数分布，但在许多情况下很有用）。另一种方法是从最终值中减去一来获得零（代价是永远得不到 Integer.MAX_VALUE）。

- BeeOnRope

你提到的分布问题非常好，对我回答中偏差的解释也很透彻。或许有一种解决方案可以根据每个位在分布中的概率来设置它们。我会尝试创建一个这样的方案，但我并不确定它是否比你的更有效率。 - sprinter

不好意思，我无法根据每个比特被设置的概率来找到一种简单的方法。数学并不像你所知道的那样简单。我承认失败。 - sprinter

我认为如果P(X = x)与1/x成比例，那么你就能理解这个问题。但是我还没有找到一个好的方法来实现它。 - Ben Millwood

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sprinter · Accepted Answer

仅提供错误答案作为信息。这并不能满足OP在问题中给出的要求。

int number = rand.nextInt(Integer.MAX_VALUE) >> rand.nextInt(Integer.SIZE);

我的非正式测试似乎表明存在预期的偏差。我以这种方式生成了100万个数字，并得到了以下对数分布（忽略零）。