3

我有一个项目，它使用 php 的 mt_rand() 来生成不同的随机整数，但我最近获得了访问真正随机位流的权限。我无法弄清楚如何创建类似于 mt_rand() 的函数，我可以从我的位流中获取两个值之间的随机整数。我怎样才能做到这一点？

4

3 回答 3

1

我想出了一个方法，但不确定它是否是最有效的方法（代码未经测试，只是演示理论）：

function RandomInteger($min, $max)
{
    $range = ($max - $min) + 1;
    $bitsNeeded = ceil( log($range, 2) );
    $number = ReadBitsAndConvertToInteger($bitsNeeded);
    if ($number < $range)
        return $number + $min;
    else if ($number > $range)
        return RandomInteger($min, $max);
}

如您所见，该功能可能会重复，这意味着将使用更多位，这就是为什么我不确定它是否是最有效的方式，就使用的位而言，这样做。

Pr(repeat) = (2^bitsNeeded - range) / (2^bitsNeeded)

Therefore, 0 < Pr(repeat) < 0.5

因此，在最坏的情况下，必须重复的机会几乎是 0.5，它开始变得不太可能需要重复超过 10 次左右，平均不到 2 次。显然，在不得不重复的机会较低的情况下，这些数字会越来越低。

于 2012-06-20T07:41:01.280 回答
1

我只会读取PHP_INT_SIZE * 8位并将结果数字压缩在您需要的范围内：

function squash($nr, $min, $max)
{
    return $min + $nr % ($max - $min);
}

另一种方式：

function squash($nr, $min, $max)
{
    return $min + round($nr / PHP_INT_MAX * ($max - $min));
}

这只是我突然想到的，为什么不直接使用你的随机流并将其推送到mt_srand()：

function squash($nr, $min, $max)
{
    mt_srand($nr);
    return mt_rand($min, $max);
}
于 2012-06-05T12:47:43.960 回答
1

让我谈谈在平均使用的随机位数方面“最佳”的随机整数生成算法。在这篇文章的其余部分，我们将假设我们有一个“真正的”随机生成器，它可以产生无偏且独立的随​​机位。

1976 年，DE Knuth 和 AC Yao 表明，任何仅使用随机位以给定概率生成随机整数的算法都可以表示为二叉树，其中随机位指示遍历树和每个叶子（端点）的方式对应一个结果。他们还给出了给定算法执行此任务所需的平均位数的下限。在这种情况下，均匀生成整数的最佳[0, n)算法平均需要最多log2(n) + 2位。在这个意义上，有很多优化算法的例子。其中一个是 J. Lumbroso (2013) 的Fast Dice Roller（在下面实现），另一个可能是数学论坛中给出的算法2004 年。另一方面，M. O'Neill 调查的所有算法都不是最优的，因为它们依赖于一次生成随机比特块。

然而，任何同样无偏的最优整数生成器通常会在最坏的情况下永远运行，正如 Knuth 和 Yao 所展示的那样。回到二叉树，n 个结果标签中的每一个都留在二叉树中，因此 [0, n) 中的每个整数都可以以 1/n 的概率出现。但是如果 1/n 有一个非终止的二元展开式（如果 n 不是 2 的幂就是这种情况），这棵二叉树必然要么——</p>

  • 具有“无限”深度，或
  • 在树的末端包括“拒绝”叶子，

在任何一种情况下，算法都会在最坏的情况下永远运行，即使它平均使用很少的随机位。（另一方面，当 n 是 2 的幂时，最佳二叉树将具有有限深度且没有拒绝节点。）快速骰子滚轮是使用“拒绝”事件来确保其无偏的算法示例；请参阅下面代码中的注释。

因此，一般来说，随机整数生成器可以是无偏的或恒定时间的（甚至两者都不是），但不能两者兼而有之。特别是，没有办法在不引入偏差的情况下“修复”不确定运行时间的最坏情况。例如，模减少（例如，mt_rand() % n) 相当于一棵二叉树，其中拒绝叶被标记的结果替换——但由于可能的结果比拒绝叶多，因此只有一些结果可以代替拒绝叶，从而引入偏差。如果您在一定次数的迭代后停止拒绝，则会产生相同类型的二叉树 - 以及相同类型的偏差。（但是，根据应用程序，这种偏差可能可以忽略不计。随机整数生成也有安全方面的问题，在这个答案中讨论太复杂了。）

请注意，我们假设我们有一个随机位生成器。如果您的答案可以通过ReadBitsAndConvertToInteger(1).

快速骰子滚子实施

以下是快速骰子滚轮的 JavaScript 实现。请注意，它使用拒绝事件和循环来确保它是公正的。 ReadBitsAndConvertToInteger(1)是一个随机位生成器（例如，在您的答案中使用）。

function randomInt(minInclusive, maxExclusive) {
  var maxInclusive = (maxExclusive - minInclusive) - 1
  var x = 1
  var y = 0
  while(true) {
    x = x * 2
    var randomBit = ReadBitsAndConvertToInteger(1)
    y = y * 2 + randomBit
    if(x > maxInclusive) {
      if (y <= maxInclusive) { return y + minInclusive }
      // Rejection
      x = x - maxInclusive - 1
      y = y - maxInclusive - 1
    }
  }
}
于 2020-07-15T16:47:46.413 回答