jeudi 3 octobre 2019

Max Value for xorShift128+ (or what's wrong with my implementation)

I'm reading up random number generators and tweaked an implementation of the xorShift128+ algorithm in javascript. I understand how bit shift operators work and how the xor bit operations work, though I'm still learning why they're useful, and why their use in xorShift128+ produces a uniform random distribution.

But more to the point, I just need to know what the range of possible numbers it works with is. It outputs integers, I'm trying to get numbers between 0 and 1. Inductively, I see that it's in the order of 2**32. So I use that as the divisor. However, when I check for uniformity, I notice a bias in the numbers. They seem to be repelled in the areas of 0.2 <= val < 0.3 and val >= 0.7.

So I've either got the calibrating divisor wrong, I've got my implementation wrong, or I'm confused about the uniformity property. Any help would be appreciated. Below is my code and my analysis:

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);



Aucun commentaire:

Enregistrer un commentaire