javascript - 生成 64 位整数的均匀分布

Question

我正在使用

var crypto = require('crypto');
var uid = crypto.pseudoRandomBytes(8);

生成 64 位 ID。

我不需要这些是真正随机的，但我希望它们在 0 和 ffffffffffffffff 之间均匀分布。然而，他们不是。以这种方式生成 1,000,000 个 64 位整数:

var bignum = require('bignum');
var crypto = require('crypto');

var randomBignum = function() { 
    return bignum.fromBuffer(crypto.pseudoRandomBytes(8));
}

var avg = randomBignum();
var avg_len = avg.bitLength();
var lengths = {};

for (var i = 0; i < 1e6; i++) {
    var big = randomBignum();
    avg = avg.add(big).div(2);
    var length = big.bitLength();
    if (typeof lengths[length] === 'undefined') { lengths[length] = 0; }
    lengths[length] += 1;
    avg_len = (avg_len + length) / 2;
}
console.log('Average integer: %s', avg);
console.log('Average bit length: %s', avg_len);
console.info('Bit length distribution: %s', require('util').inspect(lengths));

产生:

Average integer: 8386866841744540769
Average bit length: 63.11672078688376
Bit length distribution: {
  '45': 1,
  '47': 2,
  '48': 7,
  '49': 15,
  '50': 23,
  '51': 66,
  '52': 114,
  '53': 248,
  '54': 521,
  '55': 955,
  '56': 1905,
  '57': 4019,
  '58': 7742,
  '59': 15552,
  '60': 31396,
  '61': 63048,
  '62': 125182,
  '63': 249271,
  '64': 499933 }

我可能对这里的统计数据感到困惑，但这些数据并不是均匀分布的，对吧？每个字节都是单独随机生成的事实使得生成连续的 0 字节的可能性不大，因此您得到的小数字呈指数级减少。

在 Node 中生成均匀分布的 64 位 ID 的好方法是什么？我应该使用 Math.random 并将结果乘以 ffffffffffffffff 吗？

Answer 1

他们(可能)是制服!得到 0 的概率与得到 18446744073709551615 的概率相同，但在该范围内有 4611686018427387904 个数字没有前导零，只有一个有 64 个。您应该期望看到每个位计数出现大约是前一个的两倍，您的测试同意这一点。