Максимальное значение для xorShift128 + (или что не так с моей реализацией)

Question

Я читаю генераторы случайных чисел и подправил реализацию алгоритма xorShift128 + в javascript. Я понимаю, как работают операторы сдвига битов и как работают битовые операции xor, хотя я все еще изучаю, почему они полезны, и почему их использование в 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 +:

• Правильные сдвиги - это арифметические сдвиги, но они должны были быть логическими. Я не знаю, насколько это плохо, но оно определенно отличается.
• Окончательное дополнение должно быть модульным, но здесь это сумма с плавающей запятой с двойной точностью. Это очень плохо.
• Нет 128 бит состояния. Это делает PRNG менее сильным, но обнаруживать его нетривиально.

Окончательная сумма, не являющаяся модульной, делает результат неоднородным и с другим диапазономчем предполагает масштабный коэффициент: сумма двух чисел IID в [-2 ³¹ .. 2 ³¹ -1] (результат использования числа вместо uint64_t) находится в[-2 ³² .. 2 ³² -2] и смещены в сторону чисел меньшей величины. Это тот же эффект, что и сумма двух справедливых бросков кубика. Это можно обойти, добавив >>> 0, но тогда код все равно не будет реализовывать xorshift128 +.

Исправить фундаментальную проблему было бы немного болезненно, требуя эмуляции 64-битных целочисленных операций. Есть несколько библиотек, которые могут сделать эту работу за вас.