Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Seeding the random number generator in Javascript

Is it possible to seed the random number generator (Math.random) in JavaScript?

like image 899
weepy Avatar asked Feb 06 '09 17:02

weepy


People also ask

What is seeding in random number generator?

The seed() method is used to initialize the random number generator. The random number generator needs a number to start with (a seed value), to be able to generate a random number. By default the random number generator uses the current system time.

How do you generate a random number in JavaScript?

Javascript creates pseudo-random numbers with the function Math. random() . This function takes no parameters and creates a random decimal number between 0 and 1. The returned value may be 0, but it will never be 1.

What is seed in JavaScript?

seed(random2()); This gives you another functionality that JavaScript doesn't have: multiple independent random generators. That is especially important if you want to have multiple repeatable simulations running at the same time.


2 Answers

No, it is not possible to seed Math.random().

I've implemented a number of good, short and fast Pseudorandom number generator (PRNG) functions in plain JavaScript. All of them can be seeded and provide high quality numbers.

First of all, take care to initialize your PRNGs properly. To keep things simple, the generators below have no built-in seed generating procedure, but accept one or more 32-bit values as the initial seed state of the PRNG. Similar or sparse seeds (e.g. a simple seed of 1 and 2) have low entropy, and can cause correlations or other randomness quality issues, sometimes resulting in the output having similar properties (such as randomly generated levels being similar). To avoid this, it is best practice to initialize PRNGs with a well-distributed, high entropy seed.

There are many ways to do this, but here are two methods. Firstly, hash functions are very good at generating seeds from short strings. A good hash function will generate very different results even when two strings are similar, so you don't have to put much thought into the string. Here's an example seed generator based on MurmurHash3's mixing function:

function xmur3(str) {     for(var i = 0, h = 1779033703 ^ str.length; i < str.length; i++) {         h = Math.imul(h ^ str.charCodeAt(i), 3432918353);         h = h << 13 | h >>> 19;     } return function() {         h = Math.imul(h ^ (h >>> 16), 2246822507);         h = Math.imul(h ^ (h >>> 13), 3266489909);         return (h ^= h >>> 16) >>> 0;     } } 

Each subsequent call to the return function of xmur3 produces a new 32-bit hash value to be used as a seed in a PRNG. Here's how you might use it:

// Create xmur3 state: var seed = xmur3("apples"); // Output four 32-bit hashes to provide the seed for sfc32. var rand = sfc32(seed(), seed(), seed(), seed());  // Output one 32-bit hash to provide the seed for mulberry32. var rand = mulberry32(seed());  // Obtain sequential random numbers like so: rand(); rand(); 

Alternatively, simply choose some dummy data to pad the seed with, and advance the generator beforehand a few times (12-20 iterations) to mix the initial state thoroughly. This has the benefit of being simpler, and is often used in reference implementations of PRNGs, but it does limit the number of initial states:

var seed = 1337 ^ 0xDEADBEEF; // 32-bit seed with optional XOR value // Pad seed with Phi, Pi and E. // https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number var rand = sfc32(0x9E3779B9, 0x243F6A88, 0xB7E15162, seed); for (var i = 0; i < 15; i++) rand(); 

Note: the output of these PRNG functions produce a positive 32-bit number (0 to 232-1) which is then converted to a floating-point number between 0-1 (0 inclusive, 1 exclusive) equivalent to Math.random(), if you want random numbers of a specific range, read this article on MDN. If you only want the raw bits, simply remove the final division operation.

JavaScript numbers can only represent whole integers up to 53-bit resolution. And when using bitwise operations, this is reduced to 32. Modern PRNGs in other languages often use 64-bit operations, which require shims when porting to JS that can drastically reduce performance. The algorithms here only use 32-bit operations, as it is directly compatible with JS.

Now, onward to the the generators. (I maintain the full list with references and license info here)


sfc32 (Simple Fast Counter)

sfc32 is part of the PractRand random number testing suite (which it passes of course). sfc32 has a 128-bit state and is very fast in JS.

function sfc32(a, b, c, d) {     return function() {       a >>>= 0; b >>>= 0; c >>>= 0; d >>>= 0;        var t = (a + b) | 0;       a = b ^ b >>> 9;       b = c + (c << 3) | 0;       c = (c << 21 | c >>> 11);       d = d + 1 | 0;       t = t + d | 0;       c = c + t | 0;       return (t >>> 0) / 4294967296;     } } 

You may wonder what the | 0 and >>>= 0 are for. These are essentially 32-bit integer casts, used for performance optimizations. Number in JS are basically floats, but during bitwise operations, they switch into a 32-bit integer mode. This mode is processed faster by JS interpreters, but any multiplication or addition will cause it to switch back to a float, resulting in a performance hit.

Mulberry32

Mulberry32 is a simple generator with a 32-bit state, but is extremely fast and has good quality randomness (author states it passes all tests of gjrand testing suite and has a full 232 period, but I haven't verified).

function mulberry32(a) {     return function() {       var t = a += 0x6D2B79F5;       t = Math.imul(t ^ t >>> 15, t | 1);       t ^= t + Math.imul(t ^ t >>> 7, t | 61);       return ((t ^ t >>> 14) >>> 0) / 4294967296;     } } 

I would recommend this if you just need a simple but decent PRNG and don't need billions of random numbers (see Birthday problem).

xoshiro128**

As of May 2018, xoshiro128** is the new member of the Xorshift family, by Vigna & Blackman (professor Vigna was also responsible for the Xorshift128+ algorithm powering most Math.random implementations under the hood). It is the fastest generator that offers a 128-bit state.

function xoshiro128ss(a, b, c, d) {     return function() {         var t = b << 9, r = a * 5; r = (r << 7 | r >>> 25) * 9;         c ^= a; d ^= b;         b ^= c; a ^= d; c ^= t;         d = d << 11 | d >>> 21;         return (r >>> 0) / 4294967296;     } } 

The authors claim it passes randomness tests well (albeit with caveats). Other researchers have pointed out that it fails some tests in TestU01 (particularly LinearComp and BinaryRank). In practice, it should not cause issues when floats are used (such as these implementations), but may cause issues if relying on the raw lowest order bit.

JSF (Jenkins' Small Fast)

This is JSF or 'smallprng' by Bob Jenkins (2007), who also made ISAAC and SpookyHash. It passes PractRand tests and should be quite fast, although not as fast as sfc32.

function jsf32(a, b, c, d) {     return function() {         a |= 0; b |= 0; c |= 0; d |= 0;         var t = a - (b << 27 | b >>> 5) | 0;         a = b ^ (c << 17 | c >>> 15);         b = c + d | 0;         c = d + t | 0;         d = a + t | 0;         return (d >>> 0) / 4294967296;     } } 
like image 182
bryc Avatar answered Oct 08 '22 09:10

bryc


No, it is not possible to seed Math.random(), but it's fairly easy to write your own generator, or better yet, use an existing one.

Check out: this related question.

Also, see David Bau's blog for more information on seeding.

like image 30
PeterAllenWebb Avatar answered Oct 08 '22 10:10

PeterAllenWebb