2

我正在寻找一个数学方程或算法，它可以在 [0,1] 范围内按升序生成统一随机数，而无需除法运算符的帮助。我热衷于跳过除法运算，因为我正在硬件中实现它。谢谢你。

4

2 回答 2

2

以升序（或降序）顺序生成数字意味着按顺序生成它们但具有正确的分布。反过来，这意味着我们需要知道一组大小为 N 的最小值的分布，然后在每个阶段我们需要使用调节来根据我们已经看到的内容确定下一个值。从数学上讲，除了避免除法的问题外，这些都是直截了当的。

您可以使用算法从单个统一（0,1）随机数 U 生成 N 个统一（0,1）的最小值min = 1 - U**(1/N)，其中**表示求幂。换句话说，制服的第 N个根的补码与 [0,1] 范围内的 N 个制服的最小值具有相同的分布，然后可以将其缩放到您喜欢的任何其他间隔长度。

调节方面基本上是说已经生成的 k 值将吃掉原始区间的一部分，我们现在想要的是 Nk 值的最小值，缩放到剩余范围。

结合这两部分产生以下逻辑。生成 N 个制服中最小的一个，按剩余的间隔长度（第一次为 1）对其进行缩放，并将该结果作为我们生成的最后一个值。然后生成 N-1 个制服中最小的一个，按剩余的间隔长度对其进行缩放，并将其添加到最后一个制服中，为您提供下一个值。起泡、冲洗、重复，直到您完成所有操作。假设您在此之前已阅读或指定 N，以下 Ruby 实现给出了分布正确的结果：

last_u = 0.0
N.downto(1) do |i|
  p last_u += (1.0 - last_u) * (1.0 - (rand ** (1.0/i)))
end

但是我们有那个讨厌的 i th根，它使用除法。但是，如果我们提前知道 N，我们可以离线预先计算从 1 到 N 的整数的逆并将它们表。

last_u = 0.0
N.downto(1) do |i|
  p last_u += (1.0 - last_u) * (1.0 - (rand ** inverse[i]))
end

我不知道有什么方法可以在不使用求幂的情况下按顺序获得正确的分布行为。如果这是一个阻碍，你将不得不放弃过程的顺序性或均匀性要求。

于 2013-11-09T19:08:13.000 回答
2

您可以尝试所谓的“分层抽样”，这意味着您将范围划分为 bin，然后从 bin 中随机抽样。这样生成的样本比从整个区间生成的样本更均匀（更少聚集）。出于这个原因，分层抽样减少了蒙特卡洛估计的方差（我认为这对您来说并不重要，但这就是发明该方法的原因，作为一种减少方差的方法）。

按顺序生成数字是一个有趣的问题，但我的猜测是，要在整个区间内获得均匀分布，您将不得不应用一些需要更多计算的公式。如果您想最小化计算时间，我怀疑您不能比生成样本然后对其进行排序更好。

于 2013-11-09T20:41:28.750 回答