javascript - xorShift128+ 的最大值(或者我的实现有什么问题)

Question

我正在阅读随机数生成器并调整了 javascript 中 xorShift128+ 算法的实现。我了解移位运算符的工作原理以及异或位运算的工作原理，但我仍在了解它们为何有用，以及为什么它们在 xorShift128+ 中的使用会产生均匀的随机分布。

但更重要的是，我只需要知道它可以处理的可能数字的范围是多少。它输出整数，我试图得到 0 和 1 之间的数字。归纳地，我看到它的顺序是 2**32。所以我用它作为除数。然而，当我检查均匀性时，我注意到数字有偏差。它们似乎在 0.2 <= val < 0.3 和 val >= 0.7 的区域被排斥。

所以我要么校准除数错误，要么我的实现错误，要么我对均匀性属性感到困惑。任何帮助，将不胜感激。下面是我的代码和我的分析:

function xorShift128p(seed) {

    // seeds
    this.x = seed || this.x || 1;
    this.y = seed + 1 || this.y || 2;

    // swap seeds
    let x = this.y;
    let y = this.x;

    // bit manipulations that are still a little
    // obscure to me as to why they work well
    y ^= y << 23;
    y ^= y >> 17;
    y ^= x;
    y ^= x >> 26;
              
    // reset seeds
    this.x = x;
    this.y = y;

    // output, with calibration for 0-1 range.
    let realResult = x + y;
    let myCalibration = realResult / (2**32);
    return myCalibration;

}

// produce an array of 100 random numbers using xorShift128p
let rands = 
    [...new Array(100).keys()]
    .map(() => xorShift128p());

// bin the random numbers into units of 0.1 
let binCounts = 
    [...new Array(10).keys()]
    .map(key => 
        `lead: ${(key / 10).toFixed(1)}, ` + 
        `count: ${rands.filter(r => r >= key / 10 && r < (key + 1) / 10).length}`
    );    

// notice the non-uniformity
console.log(binCounts);

Answer 1

在 xorshift128+ 中，x 和 y 应该是 uint64_t。这导致此实现与实际 xorshift128+ 之间存在许多差异:

• 右移是算术移位，但应该是逻辑移位。我不知道那有多糟糕，但绝对不同。
• 最后的加法应该是模块化的，但这里是(浮点) double 和。这非常糟糕。
• 没有 128 位的状态。这会降低 PRNG 的强度，但检测起来并不容易。

最终的总和不是模块化的使得结果不均匀并且与比例因子假设的范围不同:[-2³¹ 中两个 IID 数的总和> .. 2³¹-1](使用 Number 而不是 uint64_t 的结果)在 [-2³² .. 2³²-2] 并且偏向于较小数量级的数字。这与两次公平掷骰的总和具有相同的效果。这可以通过添加 >>> 0 来解决，但是代码仍然不会实现 xorshift128+。

解决基本问题会有点痛苦，需要模拟 64 位整数运算。有一些图书馆可以为您完成这项工作。