Skip to content

Instantly share code, notes, and snippets.

@blixt

blixt/prng.js

Last active Sep 20, 2020
Embed
What would you like to do?
A very simple, seedable JavaScript PRNG. NOTE: Please read comments on why this is not a good choice.
// NOTICE 2020-04-18
// Please see the comments below about why this is not a great PRNG.
// Read summary by @bryc here:
// https://github.com/bryc/code/blob/master/jshash/PRNGs.md
// Have a look at js-arbit which uses Alea:
// https://github.com/blixt/js-arbit
/**
* Creates a pseudo-random value generator. The seed must be an integer.
*
* Uses an optimized version of the Park-Miller PRNG.
* http://www.firstpr.com.au/dsp/rand31/
*/
function Random(seed) {
this._seed = seed % 2147483647;
if (this._seed <= 0) this._seed += 2147483646;
}
/**
* Returns a pseudo-random value between 1 and 2^32 - 2.
*/
Random.prototype.next = function () {
return this._seed = this._seed * 16807 % 2147483647;
};
/**
* Returns a pseudo-random floating point number in range [0, 1).
*/
Random.prototype.nextFloat = function (opt_minOrMax, opt_max) {
// We know that result of next() will be 1 to 2147483646 (inclusive).
return (this.next() - 1) / 2147483646;
};
@madole

This comment has been minimized.

Copy link

@madole madole commented Jul 30, 2014

You dont check that the seed is a number before performing arithmetic calculations on it. potential NaN returned.

@SpaceUnicorn

This comment has been minimized.

Copy link

@SpaceUnicorn SpaceUnicorn commented Mar 22, 2017

Didn't think it would be this simple, but I guess it is! I wrote a graphic representation of the distribution here: https://www.khanacademy.org/computer-programming/prng-test/5500564014432256
A couple thousand runs show that it's pretty much uniform. Nice work 👍

@rayfoss

This comment has been minimized.

Copy link

@rayfoss rayfoss commented Aug 24, 2017

Unlike the Math.sin versions of this, this will produce the same result on Node, Chrome, Safari and Firefox... meaning I can save the seed and regenerate the same results across environments.

@momander

This comment has been minimized.

Copy link

@momander momander commented Aug 28, 2017

Very nice! This is just what I needed for my multi-player game, where some random events need to generated on all clients at the same time. With this generator all clients will get the same "random" values, without having to talk over the network.

@TBubba

This comment has been minimized.

Copy link

@TBubba TBubba commented Sep 19, 2017

Well done! Also, thanks @rayfoss for pointing out that it works across platforms, because that's exactly what I was looking for! 👍

@tommitytom

This comment has been minimized.

Copy link

@tommitytom tommitytom commented Oct 16, 2017

Do bear in mind that the float version will be affected by floating point rounding errors in different ways on different platforms - so if you want the same numbers on all platforms make sure you stick to using the integer version!

@AmaanC

This comment has been minimized.

Copy link

@AmaanC AmaanC commented Dec 1, 2017

Ended up modifying it a little to return random 32-bit signed ints, so I plotted a histogram and a random bitmap to verify the distribution was decent.

Histogram:
https://codepen.io/AmaanC/full/mqawWb/

Bitmap:
https://jsfiddle.net/amaan/nnhp57n0/

@ghost

This comment has been minimized.

Copy link

@ghost ghost commented Dec 19, 2017

Hehe. Talk about an obscure next() algorithm!

It relies on this._seed * 16807 % 2147483647 never becoming "0". If that happens, then all next() calls after that will return 0.

In other words, 1st part (this._seed * 16807) is never allowed to become 2147483647.

Luckily, the number is well-chosen. Because to get 2147483647 % 2147483647 == 0, the 1st part of the equation would have to become 2147483647. So to find out what that number would have to be, we just check 2147483647 / 16807 = 127773.168739216. So we see that we need a very specific, float number for the next() algorithm to bug out.

Luckily, as long as you seed this class with an integer, then the seed * 16807 will never produce a float and can never bug out.

Fascinating algorithm. Thank you...

PS: Your code has some funny variables: Random.prototype.nextFloat = function (opt_minOrMax, opt_max).

@backspaces

This comment has been minimized.

Copy link

@backspaces backspaces commented Jan 21, 2018

Way cool, thanks! Doesn't repeat itself for quite a while. The sin prng seems to repeat in the low millions.

This is a simpler version for floats only. It returns the PRNG function:

  function randomSeedParkMiller (seed = 123456) { // doesn't repeat b4 JS dies.
    // https://gist.github.com/blixt/f17b47c62508be59987b
    seed = seed % 2147483647
    return () => {
      seed = seed * 16807 % 2147483647
      return (seed - 1) / 2147483646
    }
  }

Here's the sin version:

  function randomSeedSin (seed = Math.PI / 4) { // ~3.4 million b4 repeat.
    // https://stackoverflow.com/a/19303725/1791917
    return () => {
      const x = Math.sin(seed++) * 10000
      return x - Math.floor(x)
    }
  }

It's written to return the function so that it can be used to replace Math.random:

Math.random = randomSeedParkMiller(seed)
@santinod

This comment has been minimized.

Copy link

@santinod santinod commented Jan 30, 2018

With the current code, initialization fails if seed = -2147483646. My suggestion:

function Random(seed) {
  this._seed = Math.abs(seed % 2147483646) + 1;
}
@juliango202

This comment has been minimized.

Copy link

@juliango202 juliango202 commented Mar 21, 2018

Thanks! There is a typo in the comment for the next() method, the upper limit is 2^31 - 2.

@bungu

This comment has been minimized.

Copy link

@bungu bungu commented Jul 9, 2018

It's possible to use this function as one-liner:

const prng = s => (typeof s!=='undefined'&&((l=s%2147483647)<=0&&(l+=2147483646)),((l=l*16807%2147483647)-1)/2147483646);
const seed = 3;

console.log(prng(seed));		// 0.000023478642127922403
console.log(prng());		// 0.3946133641475936
console.log(prng());		// 0.26681596624368425
console.log(prng());		// 0.3759503954797521
console.log(prng());		// 0.5983017120494524

Just call it again with seed to start new sequence.

@WalterBarrett

This comment has been minimized.

Copy link

@WalterBarrett WalterBarrett commented Jul 25, 2018

What's the license for this code?

@bryc

This comment has been minimized.

Copy link

@bryc bryc commented Aug 18, 2018

Do not use this kind of PRNG unless you like dealing with bugs! LCGs have a TON of quality issues, see my later post for more info.

This algorithm is known as the Lehmer LCG proposed by Park & Miller in 1988, simple but can be effective. In response to a criticism by Marsaglia in 1993, they suggested changing the multiplier to 48271.

Here's a fast implementation that uses the new multiplier instead:

// 1993 Park-Miller LCG
function LCG(s) {
    return function() {
      s = Math.imul(48271, s) | 0 % 2147483647;
      return (s & 2147483647) / 2147483648;
    }
}

// Use it like so:
var rand = LCG(123);
rand(); // skip the first number.
rand(); // returns 0.45899124443531036
rand(); // returns 0.9663704535923898

Also @bungu.. that oneliner is nice but it puts l in the global scope, bad bad! Might as well do this:

var s=3,rnd=a=>(s=s*16807%(2**31-1))/2**31

// or my faster version above, minified:
var LCG=s=>()=>(2**31-1&(s=Math.imul(48271,s)))/2**31

Even shorter 😄


Also why not look at some other 32-bit oneliners?

// a 32-bit LCG (rather than 31-bit one above)
var LCG=s=>()=>((s=Math.imul(741103597,s))>>>0)/2**32;

// original xorshift32 (honestly not that good)
var xs32=s=>()=>((s^=s<<25,s^=s>>>7,s^=s<<2)>>>0)/2**32;

// xorshift32 with knuth multiplicative
var xs32=s=>()=>(Math.imul(1597334677,s^=s<<25,s^=s>>>7,s^=s<<2)>>>0)/2**32;

// mulberry32 - an actual high quality 32-bit generator
var mb32=a=>(t)=>(a=a+1831565813|0,t=Math.imul(a^a>>>15,1|a),t=t+Math.imul(t^t>>>7,61|t)^t,(t^t>>>14)>>>0)/2**32;
@candy0414

This comment has been minimized.

Copy link

@candy0414 candy0414 commented Dec 5, 2018

i like it

@chriscauley

This comment has been minimized.

Copy link

@chriscauley chriscauley commented Dec 17, 2018

I don't think I'd call this a bug, but I recommend you "burn" the first number. It is very closely coupled to the seed. So if you choose a small seed (less than 100,000 by my estimate), your first float will always be ~0.04

for (let i=0;i<100;i++) {
  const seed = Math.floor(Math.random()*10000) // seed is 0-9,999
  console.log(new Random(seed).nextFloat()) // ~ 0.04
}

I discovered this because I'm making a video game and every enemy always moved down on their first move and every level had the same first item.

@bryc

This comment has been minimized.

Copy link

@bryc bryc commented Dec 21, 2018

@chriscauley The first number is always computed as n*16807. The highest possible seed in your example is 10000*16807 which is 0.07826369263070049 as a float.

Besides simply ignoring the first number, there's two other ways around this:

  1. Use a better LCG (bigger multipliers result in better distribution).
// 32-bit LCG (741103597 multiplier from Pierre L'Ecuyer's book)
var LCG=s=>_=>(s=Math.imul(741103597,s)>>>0)/2**32;

for(let seed=1;seed<10;seed++) console.log(seed, LCG( seed )() );
1 0.172551627503708
2 0.345103255007416
3 0.517654882511124
4 0.690206510014832
5 0.86275813751854
6 0.03530976502224803
7 0.20786139252595603
8 0.38041302002966404
9 0.552964647533372
  1. Hash the seed (best practice to ensure your seed is well distributed).
// 31-bit LCG (16807 multiplier, same algorithm as OP's)
var LCG=s=>_=>(2**31-1&(s=Math.imul(16807,s)))/2**31; 
// knuth's simple 32-bit integer hash
var hash=n=>Math.imul(n,2654435761)>>>0; 

for(let seed=1;seed<10;seed++) console.log(seed, LCG( hash(seed) )() );
1 0.5944313365034759
2 0.1888626730069518
3 0.7832940095104277
4 0.3777253460139036
5 0.9721566825173795
6 0.5665880190208554
7 0.16101935552433133
8 0.7554506920278072
9 0.34988202853128314

Personally I would use the following instead, because I don't trust the quality of LCG:

// Mulberry32, a fast high quality PRNG: https://gist.github.com/tommyettinger/46a874533244883189143505d203312c
var mb32=s=>t=>(s=s+1831565813|0,t=Math.imul(s^s>>>15,1|s),t=t+Math.imul(t^t>>>7,61|t)^t,(t^t>>>14)>>>0)/2**32;
// Better 32-bit integer hash function: https://burtleburtle.net/bob/hash/integer.html
var hash=n=>(n=61^n^n>>>16,n+=n<<3,n=Math.imul(n,668265261),n^=n>>>15)>>>0;

for(let seed=1;seed<10;seed++) console.log(seed, mb32( hash(seed) )() );

(Update Dec 2019) In fact, here is another cautionary tale about LCGs: By chance I used a random seed of 3816034944 with weird, bad behavior.

Looking at the output without the division, and in hexadecimal, the first bits are always the same.

var LCG=s=>_=>(2**31-1&(s=Math.imul(16807,s))); 
var nxt = LCG(3816034944);
for(var i = 0; i < 9; i++) console.log(nxt().toString(16))

This gives the output:

596a9180
63766a80
7349f980
7d9b4280
5c2ae180
033a9a80
7c754980
782c7280
2e113180

This shows a clear pattern in the first 8 bits of the output: 1000 000, and it happens each time, infinitely. This is mostly caused by using an even seed.

This happens even if you use a different polynomial too:

var LCG=s=>_=>(s=Math.imul(741103597,s)>>>0);
var nxt = LCG(3816034944);
for(var i = 0; i < 9; i++) console.log(nxt().toString(16))

Gives output:

32bea080
59061680
5a485480
afadba80
bc372880
f3d3fe80
84c01c80
1589e280
baa03080

So I would really avoid LCG now. If you really want a tiny oneliner, use mulberry32:

// mulberry32 - an actual high quality 32-bit generator
var mb32=a=>(t)=>(a=a+1831565813|0,t=Math.imul(a^a>>>15,1|a),t=t+Math.imul(t^t>>>7,61|t)^t,(t^t>>>14)>>>0)/2**32;

If you absolutely must use an LCG, using an increment seems to improve the situation:

var LCG=s=>_=>(s=9**8+Math.imul(s,9**9)>>>0);
@nanodeath

This comment has been minimized.

Copy link

@nanodeath nanodeath commented Apr 18, 2020

I strongly recommend checking out this page by @bryc for information on better JS PRNG implementations.

@blixt

This comment has been minimized.

Copy link
Owner Author

@blixt blixt commented Apr 18, 2020

Thanks for all the comments here! I'll add a clear notice in the top of this gist to ask the reader to read up on it!

This is a very old gist, and after making it I found Alea to be a good performance/quality compromise in JS and made this package: https://github.com/blixt/js-arbit

I set up dieharder tests in the js-arbit repo if you wanna compare it to other PRNGs.

@nanodeath

This comment has been minimized.

Copy link

@nanodeath nanodeath commented Apr 19, 2020

@blixt this page happens to be the #2 result on Google for "javascript prng" 🙂

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.