Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Math.random and web programming in JavaScript

According to this Stack Overflow thread, Math.random() in JavaScript depends on the browser or the operating system. Basically, it implies that JavaScript does not have a standard algorithm for generating uniform random variables. This thread seems to suggest that Chrome's uniform random number algorithm is particularly bad.

In my program I try to understand how the user behaves based on some information plus random noise. I use a Box-Muller transform on numbers generated by Math.random() to generate Gaussian random numbers. Does this mean that users using one browser will be experiencing different types of noise than others? Note I use Box Muller because I don't care about speed, but I know it can be particularly sensitive to how the pseudo random numbers are generated. There seems to be lots of threads about why Math.random() is bad, but not so much within the thread on what to actually use instead. What is the best practice? Is there something that I should particularly look out for because I am using Box-Muller to convert to Gaussian numbers?

like image 650
WetlabStudent Avatar asked Oct 22 '13 01:10

WetlabStudent


2 Answers

There's an xor-shift based RNG at http://en.wikipedia.org/wiki/Xorshift with good randomness properties that should port fairly readily to JavaScript:

EDIT done:

(function () {
    var x = 123456789;
    var y = 362436069;
    var z = 521288629;
    var w = 88675123;
    var f = Math.pow(2, -32);

    Object.defineProperty(Math, 'xor128', {
        value: function () {
            var t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));

            return (w >>> 0) * f;  // convert to floating point          
        }
    });

})();

NB: this only uses 32 bits of the 128 generated to produce the floating point result. In theory you could combine another 20 bits from one of the other state variables to produce 52 bits of result.

The most significant issue with it I can see is that it doesn't support seeding - it'll always generate the same sequence.

like image 76
Alnitak Avatar answered Oct 26 '22 18:10

Alnitak


A Box-Muller transform only works on uniformly distributed input. According to MDN (last example), Math.random() will not generate uniformly distributed numbers.

The ECMAScript specification says the following about Math.random():

Returns a Number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments.

So, it's up to the browser. A browser might but doesn't have to implement a perfectly uniformly distributed random number generator.

Therefore you cannot reliably implement a cross-browser Box-Muller transform in Javascript on the browser side using Math.random()

like image 37
thwd Avatar answered Oct 26 '22 18:10

thwd