重新映射到新范围后保持均匀分布

Question

因为这是关于将一个均匀分布重新映射到另一个具有不同范围的分布，所以这不是一个 PHP 问题，尽管我使用的是 PHP。

我有一个加密安全的随机数生成器，它为我提供 0 和 PHP_INT_MAX 之间均匀分布的整数（均匀离散分布）。

如何重新映射这些结果以有效地适应不同的范围？

目前我正在使用 $mappedRandomNumber = $randomNumber % ($range + 1) + $min，其中 $range = $max - $min，但显然不起作用，因为范围内的第一个 PHP_INT_MAX%$range 整数有更高的机会被选中，打破了分布的均匀性。

Answer 1

好吧，对 PHP 的了解为零，我绝对有资格成为专家，所以

在心理上转换为浮点数 U[0,1)

f = r / PHP_MAX_INT

然后做

mapped = min + f*(max - min)

回到整数

mapped = min + (r * max - r * min)/PHP_MAX_INT

如果计算是通过 64 位数学完成的，并且 PHP_MAX_INT 是 2^31 它应该可以工作

Answer 2

这就是我最终所做的。 PRNG 101（如果不合适，忽略并重新生成）。不是很复杂，但很简单：

public function rand($min = 0, $max = null){

  // pow(2,$numBits-1) calculated as (pow(2,$numBits-2)-1) + pow(2,$numBits-2) 
  // to avoid overflow when $numBits is the number of bits of PHP_INT_MAX
  $maxSafe = (int) floor(
    ((pow(2,8*$this->intByteCount-2)-1) + pow(2,8*$this->intByteCount-2))   
    / 
    ($max - $min)
  ) * ($max - $min);

  // discards anything above the last interval N * {0 .. max - min -1} 
  // that fits in {0 ..  2^(intBitCount-1)-1}
  do {
    $chars = $this->getRandomBytesString($this->intByteCount);
    $n = 0;
    for ($i=0;$i<$this->intByteCount;$i++) {$n|=(ord($chars[$i])<<(8*($this->intByteCount-$i-1)));}
  } while (abs($n)>$maxSafe);

  return (abs($n)%($max-$min+1))+$min;

}

欢迎任何改进。

（完整代码在 https://github.com/elcodedocle/cryptosecureprng/blob/master/CryptoSecurePRNG.php）

Answer 3

这是我将如何做的草图：

假设您在 [A, B) 范围内有均匀的随机整数分布，这就是您的随机数生成器所提供的。让L = B - A。设 P 为 2 的最高次方，使得 P <= L。设 X 为该范围内的样本。首先计算Y = X - A。如果 Y >= P，丢弃它并从新的 X 开始，直到你得到一个适合的 Y。

现在 Y 包含 log2(P) 个均匀随机位 - 零扩展到 log2(P) 个位。

现在我们有了统一的随机位生成器，可用于根据需要提供任意数量的随机位。

要生成目标范围内的数字，让 [A_t, B_t) 成为目标范围。让L_t = B_t - A_t。令 P_t 为满足 P_t >= L_t 的最小 2 次方。读取 log2(P_t) 个随机位并从中生成一个整数，我们称之为 X_t。如果 X_t >= L_t，丢弃它并重试，直到你得到一个合适的数字。您在所需范围内的随机数将为 L_t + A_t.

实施注意事项：如果您的 L_t 和 L 是 2 的幂，您永远不必丢弃任何东西。如果不是，那么即使在最坏的情况下，您也应该在平均不到 2 次试验中得到正确的数字。

重新映射到新范围后保持均匀分布

Keep uniform distribution after remapping to a new range

random

probability

discrete-mathematics

prng

probability-density