使用浮点源均匀分布整数
Uniform distribution of integers using floating point source
在 JavaScript 中获取 [0, n) 范围内的随机整数的标准方法 - 或仅提供 random() 函数的任何其他语言 returns 中的浮点数范围 [0,1) - 是使用 Math.floor(Math.random() * n)。
假设我们对有理数集进行运算，那么这背后的数学就很简单了。问题是：由于 IEEE-754 浮点数的所有复杂性，最终的分布真的是均匀的吗？
考虑到一个浮点数和下一个更高的浮点数之间的差距随着它们变大而增加，我认为这应该引入某种偏向于较小数字的偏见。
根据http://es5.github.io/x15.8.html#x15.8.2.14
Math.random
的功能
Returns a Number value with positive sign, greater than or equal to 0
but less than 1, chosen randomly or pseudo randomly with approximately
uniform distribution over that range, using an
implementation-dependent algorithm or strategy. This function takes no
arguments.
这已经超出了我的理解范围，对不起，我没有什么可以贡献的了
假设 random() 返回一个介于 0..1.
之间的数字
如果结果是单精度浮点数，那么基于尾数的熵只有 23 位。
如果结果是双精度浮点数，那么基于尾数的熵只有 52 位。
所以 floor(random() * N) 只有在 N 小于 2^24 或 2^53 的情况下才是统一的。
编辑 这里有一些关于浮点数的最大连续整数的信息 http://www.mathworks.com/help/matlab/ref/flintmax.html
我假设你说 "the gap between one floating point number and the next higher one increases as they grow larger" 是基于以下内容：
在 IEEE-754 中你有一个固定大小的尾数，它允许在 [1,2) 范围内使用统一的 "random" 值，并且在 [2,4] 中有相同数量的可能值) 这是范围的两倍，所以我们在可能值之间得到两倍的间距，对于 [4,8)，等等也是两倍。
现在，当他们谈论为 [0,1) 生成的随机数的属性时，我还没有查看“..，使用依赖于实现的算法或策略”背后的技术细节，但是由于上述考虑是如此微不足道，我假设随机生成器程序员已经意识到这一点并用 "implementation-dependent algo...".
来处理它
因此，作为一个天真的人，我相信关于（我的假设）你怀疑的理由没有什么可担心的。事实上，我可能认为，如果您可以为尾数生成统一的随机值，然后始终设置相同的指数，这样这些值属于 [1,2)，您就可以从所有内容中减去 1 并获得适当的分布对于 [0,1].
如果 Math.random（或等价物）从对应于 [0, 1) 范围内的浮点数的那些位模式中生成一个均匀分布的位模式，那么它会产生一个极端有偏见的样本。 [0.25, 0.5) 中的可表示浮点数与 [0.5, 1.0) 中的可表示浮点数一样多，这也是 [0.125, 0.25) 中可表示值的相同数量。等等。简而言之，均匀分布的位模式将导致千分之一的值介于 0.5 和 1.0 之间。 （假设双精度浮点数。）
幸运的是，这不是 Math.random 所做的。获得均匀分布数（而不是位模式）的一种简单方法是在 [1.0, 2.0) 中生成一个均匀分布的位模式，然后减去 1.0；这是一个相当普遍的策略。
无论如何，Math.floor(Math.random() * n) 的最终结果分布不是很均匀，除非 n 是 2 的幂，因为量化偏差。 Math.random可能返回的浮点数的个数是2的次方，如果n不是2的次方，则不可能将可能的浮点数精确均匀分布[0, n) 中整数的所有值。如果Math.randomreturns是一个双精度浮点数，而n不是很大，这个偏差很小，但肯定存在。
不，对于 n 的大多数值，生成的分布不会完全均匀。对于较小的值，它会非常接近均匀，以至于您很难检测到与均匀分布的任何差异，但随着 n 变大，偏差会变得明显。
为了说明，这里有一些Python代码（不是JavaScript，对不起，但是原理是一样的）：
from collections import Counter
from random import random
def badrand(n):
return int(random() * n)
print(Counter(badrand(6755399441055744) % 3 for _ in range(10000000)))
这将生成 [0, 6755399441055744) 范围内的 1000 万个随机整数，将这些整数中的每一个减去模 3，并计算余数为 0、1 或 2 的次数。如果我们生成这些整数一致，我们希望余数模 3 大致均匀分布，因此我们希望计数相似。
这是我机器上 运行 的示例结果：
Counter({1: 3751915, 0: 3334643, 2: 2913442})
也就是说，1 的余数 比 0 发生的可能性显着 ，而后者又比 0 发生的可能性大得多2 的剩余部分。这里的差异 way 太大，无法用随机变化来解释。
所以哪里出了问题？ Python 的 random() 函数质量相对较高，基于 Mersenne Twister，因此我们不太可能看到基本随机数生成器导致的统计问题。发生的事情是 random() 生成 2^53 个（大致）同样可能的结果之一 - 每个结果都是 x / 2^53 形式的数字，对于 [0, 2^53) 范围内的某个整数 x ].现在在 badrand 调用中，我们有效地将这些结果映射到 6755399441055744 可能的输出。现在这个值不是随机选择的（哈！）；它正好是 2^53 的 3/4。这意味着在可能的最均匀分布下，可能的 badrand 输出值的 2/3 正好被 2^53 个可能的 random() 输出值中的一个命中，而其他 1/3 是被 2^53 个可能的 random() 输出值中的 two 击中。也就是说，某些潜在输出的发生概率是其他输出的 两倍 。所以我们离制服还有很长的路要走。
您将在 JavaScript 中看到相同的效果。在 Chrome 的情况下，似乎 there are only 2^32 distinct results 来自 Math.random()，所以你应该能够找到像上面这样的效果 n 小于（但接近）2 ^32.
当然，对于小 n，同样的效果也适用：如果 n = 5，那么因为 5 不是 2^32 的约数，所以我们不可能可以在 5 个期望结果之间完美均匀地分配所有 2^32 可能的 Math.random() 结果：我们可以希望的最好结果是 5 个结果中的 4 个出现在 858993459 个可能的 random() 结果中，而第五个出现在 random() 个结果中的 858993460 个。但这种分布将非常接近均匀，以至于几乎不可能找到任何统计测试来告诉你不同的结果。因此，出于实际目的，使用小 n.
应该是安全的
Python 2 中的 http://bugs.python.org/issue9025. That bug was solved for Python 3 by moving away from the int(random() * n) method of computing these numbers. The bug still remains 中有一个相关的 Python 错误可能很有趣。
在 JavaScript 中获取 [0, n) 范围内的随机整数的标准方法 - 或仅提供 random() 函数的任何其他语言 returns 中的浮点数范围 [0,1) - 是使用 Math.floor(Math.random() * n)。
假设我们对有理数集进行运算，那么这背后的数学就很简单了。问题是：由于 IEEE-754 浮点数的所有复杂性，最终的分布真的是均匀的吗？
考虑到一个浮点数和下一个更高的浮点数之间的差距随着它们变大而增加，我认为这应该引入某种偏向于较小数字的偏见。
根据http://es5.github.io/x15.8.html#x15.8.2.14
Math.random
的功能Returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments.
这已经超出了我的理解范围，对不起，我没有什么可以贡献的了
假设 random() 返回一个介于 0..1.
之间的数字如果结果是单精度浮点数，那么基于尾数的熵只有 23 位。
如果结果是双精度浮点数，那么基于尾数的熵只有 52 位。
所以 floor(random() * N) 只有在 N 小于 2^24 或 2^53 的情况下才是统一的。
编辑 这里有一些关于浮点数的最大连续整数的信息 http://www.mathworks.com/help/matlab/ref/flintmax.html
我假设你说 "the gap between one floating point number and the next higher one increases as they grow larger" 是基于以下内容：
在 IEEE-754 中你有一个固定大小的尾数，它允许在 [1,2) 范围内使用统一的 "random" 值，并且在 [2,4] 中有相同数量的可能值) 这是范围的两倍，所以我们在可能值之间得到两倍的间距，对于 [4,8)，等等也是两倍。
现在，当他们谈论为 [0,1) 生成的随机数的属性时，我还没有查看“..，使用依赖于实现的算法或策略”背后的技术细节，但是由于上述考虑是如此微不足道，我假设随机生成器程序员已经意识到这一点并用 "implementation-dependent algo...".
来处理它因此，作为一个天真的人，我相信关于（我的假设）你怀疑的理由没有什么可担心的。事实上，我可能认为，如果您可以为尾数生成统一的随机值，然后始终设置相同的指数，这样这些值属于 [1,2)，您就可以从所有内容中减去 1 并获得适当的分布对于 [0,1].
如果 Math.random（或等价物）从对应于 [0, 1) 范围内的浮点数的那些位模式中生成一个均匀分布的位模式，那么它会产生一个极端有偏见的样本。 [0.25, 0.5) 中的可表示浮点数与 [0.5, 1.0) 中的可表示浮点数一样多，这也是 [0.125, 0.25) 中可表示值的相同数量。等等。简而言之，均匀分布的位模式将导致千分之一的值介于 0.5 和 1.0 之间。 （假设双精度浮点数。）
幸运的是，这不是 Math.random 所做的。获得均匀分布数（而不是位模式）的一种简单方法是在 [1.0, 2.0) 中生成一个均匀分布的位模式，然后减去 1.0；这是一个相当普遍的策略。
无论如何，Math.floor(Math.random() * n) 的最终结果分布不是很均匀，除非 n 是 2 的幂，因为量化偏差。 Math.random可能返回的浮点数的个数是2的次方，如果n不是2的次方，则不可能将可能的浮点数精确均匀分布[0, n) 中整数的所有值。如果Math.randomreturns是一个双精度浮点数，而n不是很大，这个偏差很小，但肯定存在。
不，对于 n 的大多数值，生成的分布不会完全均匀。对于较小的值，它会非常接近均匀，以至于您很难检测到与均匀分布的任何差异，但随着 n 变大，偏差会变得明显。
为了说明，这里有一些Python代码（不是JavaScript，对不起，但是原理是一样的）：
from collections import Counter
from random import random
def badrand(n):
return int(random() * n)
print(Counter(badrand(6755399441055744) % 3 for _ in range(10000000)))
这将生成 [0, 6755399441055744) 范围内的 1000 万个随机整数，将这些整数中的每一个减去模 3，并计算余数为 0、1 或 2 的次数。如果我们生成这些整数一致，我们希望余数模 3 大致均匀分布，因此我们希望计数相似。
这是我机器上 运行 的示例结果：
Counter({1: 3751915, 0: 3334643, 2: 2913442})
也就是说，1 的余数 比 0 发生的可能性显着 ，而后者又比 0 发生的可能性大得多2 的剩余部分。这里的差异 way 太大，无法用随机变化来解释。
所以哪里出了问题？ Python 的 random() 函数质量相对较高，基于 Mersenne Twister，因此我们不太可能看到基本随机数生成器导致的统计问题。发生的事情是 random() 生成 2^53 个（大致）同样可能的结果之一 - 每个结果都是 x / 2^53 形式的数字，对于 [0, 2^53) 范围内的某个整数 x ].现在在 badrand 调用中，我们有效地将这些结果映射到 6755399441055744 可能的输出。现在这个值不是随机选择的（哈！）；它正好是 2^53 的 3/4。这意味着在可能的最均匀分布下，可能的 badrand 输出值的 2/3 正好被 2^53 个可能的 random() 输出值中的一个命中，而其他 1/3 是被 2^53 个可能的 random() 输出值中的 two 击中。也就是说，某些潜在输出的发生概率是其他输出的 两倍 。所以我们离制服还有很长的路要走。
您将在 JavaScript 中看到相同的效果。在 Chrome 的情况下，似乎 there are only 2^32 distinct results 来自 Math.random()，所以你应该能够找到像上面这样的效果 n 小于（但接近）2 ^32.
当然，对于小 n，同样的效果也适用：如果 n = 5，那么因为 5 不是 2^32 的约数，所以我们不可能可以在 5 个期望结果之间完美均匀地分配所有 2^32 可能的 Math.random() 结果：我们可以希望的最好结果是 5 个结果中的 4 个出现在 858993459 个可能的 random() 结果中，而第五个出现在 random() 个结果中的 858993460 个。但这种分布将非常接近均匀，以至于几乎不可能找到任何统计测试来告诉你不同的结果。因此，出于实际目的，使用小 n.
Python 2 中的 http://bugs.python.org/issue9025. That bug was solved for Python 3 by moving away from the int(random() * n) method of computing these numbers. The bug still remains 中有一个相关的 Python 错误可能很有趣。