gpt4 book ai didi

javascript - 使用浮点源均匀分布整数

转载 作者:搜寻专家 更新时间:2023-11-01 05:30:11 25 4
gpt4 key购买 nike

在 JavaScript 中获取 [0, n) 范围内的随机整数的标准方法——或任何其他仅提供返回 [0,1) 范围内的 float 的 random() 函数的语言——是使用Math.floor(Math.random() * n)

假设我们对有理数集进行运算,那么这背后的数学就很简单了。问题是:由于 IEEE-754 float 的所有复杂性,最终的分布真的是均匀的吗?

考虑到一个 float 和下一个更高的 float 之间的差距随着它们变大而增加,我认为这应该引入某种偏向于较小数字的偏差。

最佳答案

不,对于 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 的余数。这里的差异方式太大,无法用随机变化来解释。

那么到底出了什么问题呢? Python 的random() 函数质量比较高,基于Mersenne Twister。 ,所以我们不太可能看到由基本随机数生成器引起的统计问题。发生的事情是 random() 生成 2^53(大致)等可能结果之一 - 每个结果都是 x/2^53 形式的数字,表示某个整数x[0, 2^53) 范围内。现在在 badrand 调用中,我们有效地将这些结果映射到 6755399441055744 可能的输出。现在这个值不是随机选择的(哈!);它正好是 2^53 的 3/4。这意味着在可能的最均匀分布下,2/3 可能的 badrand 输出值恰好被 2^53 个可能的 random() 输出值之一击中,而另外 1/3 被 2^53 个可能的 random() 输出值中的 两个 击中。也就是说,某些潜在输出的发生概率是其他输出的两倍。所以我们离制服还有很长的路要走。

您将在 JavaScript 中看到相同的效果。对于 Chrome,似乎 there are only 2^32 distinct results来自 Math.random(),因此您应该能够找到类似上面的 n 小于(但接近)2^32 的效果。

当然,同样的效果也适用于小的n:如果n = 5,那么因为5不是2^32 我们无法将所有 2^32 可能的 Math.random() 结果完美均匀地分布在 5 个期望结果之间:我们最好希望的是 5 个结果中的 4 个出现在 858993459 个可能的 random() 结果中,而第五个出现在 858993460 个 random() 结果中.但这种分布将非常接近均匀,以至于几乎不可能找到任何统计测试来告诉你不同的结果。因此,出于实际目的,使用较小的 n 应该是安全的。

http://bugs.python.org/issue9025 上有一个相关的 Python 错误可能很有趣.通过放弃计算这些数字的 int(random() * n) 方法,Python 3 解决了该错误。错误依旧remains不过在 Python 2 中。

关于javascript - 使用浮点源均匀分布整数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32360671/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com