随机数位数的分布

Question

我在尝试用JavaScript实现UUID生成器时遇到了这种奇怪的现象.

基本上,在JavaScript中,如果我Math.random()使用Node上的内置生成大量随机数4.2.2:

var records = {};
var l;
for (var i=0; i < 1e6; i += 1) {
  l = String(Math.random()).length;
  if (records[l]) {
    records[l] += 1;
  } else {
    records[l] = 1;
  }
}
console.log(records);

数字位数有一个奇怪的模式:

{ '12': 1,
  '13': 11,
  '14': 65,
  '15': 663,
  '16': 6619,
  '17': 66378,
  '18': 611441,
  '19': 281175,
  '20': 30379,
  '21': 2939,
  '22': 282,
  '23': 44,
  '24': 3 }

我认为这是V8的随机数生成器的怪癖,但类似的模式出现在Python 3.4.3:

12 : 2
13 : 5
14 : 64
15 : 672
16 : 6736
17 : 66861
18 : 610907
19 : 280945
20 : 30455
21 : 3129
22 : 224

Python代码如下:

import random
random.seed()
records = {}
for i in range(0, 1000000):
    n = random.random()
    l = len(str(n))
    try:
        records[l] += 1
    except KeyError:
        records[l] = 1;

for i in sorted(records):
    print(i, ':', records[i])

预期从18到以下的模式:如果随机数应该有20位,那么如果数字的最后一位是0,它实际上只有19位数.如果随机数发生器是好的,那么发生这种情况的概率大约是1/10.

但是为什么这个模式在19岁及以后都被逆转了？

我想这与浮点数的二进制表示有关,但我无法弄明白为什么.

Answer 1

原因确实与浮点表示有关.浮点数表示具有它可以表示的最大(二进制)数字数和有限的指数值范围.现在,当您在不使用科学记数法的情况下打印出来时,在某些情况下,您可能需要在有效数字开始跟随之前的小数点后面有一些零.

您可以通过打印转换为时间最长的随机数来可视化此效果string:

var records = {};
var l, r;
for (var i=0; i < 1e6; i += 1) {
    r = Math.random();
    l = String(r).length;
    if (l === 23) {
        console.log(r);
    }
    if (records[l]) {
        records[l] += 1;
    } else {
        records[l] = 1;
    }
}

这只会打印23个长的字符串,你会得到这样的数字:

0.000007411070483631654
0.000053944830052166104
0.000018188989763578967
0.000029525788901141325
0.000009613635131744402
0.000005937417234758158
0.000021099748521158368

注意第一个非零数字之前的零.这些实际上并未存储在浮点表示的数字部分中,而是由其指数部分隐含.

如果您要取出前导零,然后计算:

var records = {};
var l, r, s;
for (var i=0; i < 1e6; i += 1) {
    r = Math.random();
    s = String(r).replace(/^[0\.]+/, '');
    l = s.length;

    if (records[l]) {
        records[l] += 1;
    } else {
        records[l] = 1;
    }
}

......你会得到不那么奇怪的结果.

但是,您会看到一些不规则性,这是由于如何javascript将微小数字转换为string:当它们变得太小时,在表示中使用科学记数法string.您可以使用以下脚本看到这一点(不确定每个浏览器是否都有相同的断点,因此您可能需要使用该数字):

var i = 0.00000123456789012345678;
console.log(String(i), String(i/10));

这给了我以下输出:

0.0000012345678901234567 1.2345678901234568e-7

因此,非常小的数字将得到更固定的string长度,通常是22个字符,而在非科学记数法中,长度为23是常见的.这也影响了我提供的第二个脚本,长度22将获得比23更多的命中.

应该注意的是javascript,转换为string二进制表示时不会切换到科学记数法:

var i = 0.1234567890123456789e-120;
console.log(i.toString(2));

以上将打印超过450个二进制数字的字符串!

Answer 2

这是因为有些值是这样的：

0.00012345...

因此它们更长。