为什么这个随机值有一个25/75分布而不是50/50?

编辑:所以基本上我想写的是1位散列double

我想用一个50/50的false将一个double映射为truefalse 。 为此,我编写了一些随机数字的代码(只是作为一个例子,我想用规则的数据来使用它,仍然得到50/50的结果) ,检查它们的最后一位,如果是1,则增加y如果n它是0。

然而,这个代码不断地导致25% y和75% n 。 为什么不是50/50? 为什么这么奇怪,但是直截了当(1/3)的分布呢?

 public class DoubleToBoolean { @Test public void test() { int y = 0; int n = 0; Random r = new Random(); for (int i = 0; i < 1000000; i++) { double randomValue = r.nextDouble(); long lastBit = Double.doubleToLongBits(randomValue) & 1; if (lastBit == 1) { y++; } else { n++; } } System.out.println(y + " " + n); } } 

示例输出:

 250167 749833 

因为nextDouble是这样工作的:( 来源 )

 public double nextDouble() { return (((long) next(26) << 27) + next(27)) / (double) (1L << 53); } 

next(x)产生x随机位。

现在为什么这很重要? 由于第一部分(分割之前)产生的数字大约有一半小于1L << 52 ,因此它们的有效数并不完全填充它可以填充的53位,这意味着有效数的最低有效位总是零为那些。


由于受到了大量的关注,下面是关于Java(以及其他许多语言)中实现double精度的一些额外解释,以及为什么它在这个问题上至关重要。

基本上, double看起来像这样:( 来源 )

双重布局

在这幅图中不可见的一个非常重要的细节是数字被“标准化” 1 ,使得53比特部分以1开始(通过select指数使得它是这样的),那么1被省略。 这就是为什么图像显示52位的分数(有效数),但有53位有效。

规范化意味着如果在nextDouble的代码中第53位被设置,则该位是隐含的前导1并且它将消失,而其余的52位被复制到所得到的double 。 如果该位没有被设置,剩下的位必须被左移,直到被置位。

平均而言,一半的生成数据属于有效数据完全没有左移的情况(大约一半有0作为它们的最低有效位),而另一半移位至less1(或者完全是零),所以它们的最低有效位总是0。

1:并不总是,显然它不能做零,它没有最高的1.这些数字被称为denormal或subnormal数字,见维基百科:非正规数 。

从文档 :

nextDouble方法由类Random实现,就像通过下面的方法:

 public double nextDouble() { return (((long)next(26) << 27) + next(27)) / (double)(1L << 53); } 

但它也说明了以下内容(重点是我的):

[在早期的Java版本中,结果被错误地计算为:

  return (((long)next(27) << 27) + next(27)) / (double)(1L << 54); 

这看起来似乎是等价的(如果不是更好的话),但实际上由于浮点数四舍五入的偏差,引入了大的非均匀性:有效数的低位为0的可能性是三倍比它将是1 ! 这种不一致在实践中可能并不重要,但我们力求完美。]

至less从Java 5开始,这个笔记就已经存在了(Java <= 1.4的文档在loginwall之后,懒得去检查)。 这很有趣,因为即使在Java 8中,问题显然依然存在。也许“固定”版本从未被testing过?

考虑到如何表示浮点数,这个结果并不让我吃惊。 假设我们有一个只有4位精度的非常短的浮点types。 如果我们要生成一个0到1之间的随机数,并且统一分布,则会有16个可能的值:

 0.0000 0.0001 0.0010 0.0011 0.0100 ... 0.1110 0.1111 

如果他们在机器上看起来如此,那么可以testing低阶位以获得50/50的分配。 但是,IEEE浮点数表示为尾数2倍的幂次; float中的一个字段是2的幂(加上一个固定的偏移量)。 2的幂被select为使得“尾数”部分总是> 1.0和<2.0的数字。 这意味着,实际上, 0.0000以外的数字将表示如下:

 0.0001 = 2^(-4) x 1.000 0.0010 = 2^(-3) x 1.000 0.0011 = 2^(-3) x 1.100 0.0100 = 2^(-2) x 1.000 ... 0.0111 = 2^(-2) x 1.110 0.1000 = 2^(-1) x 1.000 0.1001 = 2^(-1) x 1.001 ... 0.1110 = 2^(-1) x 1.110 0.1111 = 2^(-1) x 1.111 

(二进制前的1是一个隐含的值;对于32位和64位的浮点数,实际上没有位被用来保存这个1

但是看上面的内容应该certificate为什么,如果将表示转换为位并查看低位,则可以得到75%的时间。 这是由于所有值小于0.5(二进制0.1000 ),这是可能值的一半,他们的尾数转移,导致0出现在低位。 当尾数有52位(不包括隐含1)作为double精度时,情况基本相同。

(实际上,正如@sneftel在评论中提出的那样,我们可以在分布中包含超过16个可能的值,通过生成:

 0.0001000 with probability 1/128 0.0001001 with probability 1/128 ... 0.0001111 with probability 1/128 0.001000 with probability 1/64 0.001001 with probability 1/64 ... 0.01111 with probability 1/32 0.1000 with probability 1/16 0.1001 with probability 1/16 ... 0.1110 with probability 1/16 0.1111 with probability 1/16 

但是我不确定这是大多数程序员所期望的那种分布,所以这可能是不值得的。 另外,当使用这些值来生成整数时,它并不会带来太多的收益,因为随机的浮点值经常是这样。)