Skip to content

Instantly share code, notes, and snippets.

@bryc
Last active March 15, 2022 12:01
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bryc/38a86416e8fa940e009adb15821f36d7 to your computer and use it in GitHub Desktop.
Save bryc/38a86416e8fa940e009adb15821f36d7 to your computer and use it in GitHub Desktop.
PRNGs
/*
Optimized Alea
----------------------
Based on Alea by Johannes Baagøe (2010) which is based on MWC by George Marsaglia and Arif Zaman (1991).
Should be fast and pass BigCrush statistical test suite. It's quite fast but the quality is unverified.
Used like so:
var rand = Alea("test123");
rand(); // 0.7390809920616448
rand(); // 0.3916741746943444
*/
function Alea(seed) {
if(seed === undefined) {seed = +new Date() + Math.random();}
function Mash() {
var n = 4022871197;
return function(r) {
for(var t, s, u = 0, e = 0.02519603282416938; u < r.length; u++)
s = r.charCodeAt(u), f = (e * (n += s) - (n*e|0)),
n = 4294967296 * ((t = f * (e*n|0)) - (t|0)) + (t|0);
return (n|0) * 2.3283064365386963e-10;
}
}
return function() {
var m = Mash(), a = m(" "), b = m(" "), c = m(" "), x = 1, y;
seed = seed.toString(), a -= m(seed), b -= m(seed), c -= m(seed);
a < 0 && a++, b < 0 && b++, c < 0 && c++;
return function() {
var y = x * 2.3283064365386963e-10 + a * 2091639; a = b, b = c;
return c = y - (x = y|0);
};
}();
}
/*
JSF (Jenkins Small Fast)
----------------------
A PRNG by Bob Jenkins made in 2007 (http://burtleburtle.net/bob/rand/smallprng.html)
Should be pretty fast and pass Diehard as well as PractRand. Appears to fail some BigCrush tests.
Used like so:
var rand = JSF(123);
rand(); // 0.098275076597929
rand(); // 0.8299110839143395
*/
function JSF(seed) {
function jsf() {
var e = s[0] - (s[1]<<27 | s[1]>>5);
s[0] = s[1] ^ (s[2]<<17 | s[2]>>15),
s[1] = s[2] + s[3],
s[2] = s[3] + e, s[3] = s[0] + e;
return (s[3] >>> 0) / 4294967295; // 2^32-1
}
seed >>>= 0;
var s = [0xf1ea5eed, seed, seed, seed];
for(var i=0;i<20;i++) jsf();
return jsf;
}
/*
LCG (m = 2^31-1, a = 48271, c = 0)
----------------------
A specific LCG configuration as suggested by Park & Miller (1993). Amended from their previous suggestion of a = 16807 (1988).
It's not easy to find suitable parameters for an LCG generator as it requires much statistical tests, and LCG is regarded as
an inferior and insecure method of pseudorandom number generation anyway. However based on basic tests, these additional configurations
are noteworthy:
m = 0, a = 0, c = 0
m = 2^31-1, a = 16807, c = 0
m = 2^31-1, a = 48271, c = 0
m = 2^31-1, a = 39373, c = 0
m = 2^31-1, a = 69621, c = 0
m = 2^31, a = 65539, c = 0
m = 2^32, a = 16843009, c = 826366247
m = 2^32, a = 214013, c = 2531011
m = 2^32, a = 1664525, c = 1013904223
Used like so (positive numerical inputs only):
var rand = LCG(1234);
rand(); // 0.9300422426313162
rand(); // 0.06911496166139841
Note: Running the initial seed or Math.random through lcg() as shown below is intended to improve the
random quality of the first returned result.
*/
function LCG(seed) {
function lcg(seed) {return 48271 * seed % 2147483647}
seed = lcg(seed || Math.random());
return function() {return (seed = lcg(seed)) / 2147483646 } // 2^31-2
}
/*
xoroshiro64
----------------------
(Note: this is a continuation of xoshiro, so read its comments first.)
The xoroshrio family has some 32-bit variants we can use, however they only have a 64-bit state.
I would say it's superior to xorshift32 but possibly inferior to xorshift128. Should be quite fast.
Good if you are only working with 64-bit hashes.
Used like so:
var rand = xoroshiro64ss([9**9, 8**9, 7**9, 6**9]); // needs some initial state/seed - use hash algorithm.
rand(); // returns 0.8493802803217854
rand(); // returns 0.9016569563890009
*/
function xoroshiro64ss(s) {
return function() {
var s0 = s[0], s1 = s[1];
var m = Math.imul(s0, 0x9E3779BB),
r = (m<<5 | m>>>27) * 5;
s1 ^= s0;
s[0] = (s0<<26 | s0>>>6) ^ s1 ^ (s1 << 9);
s[1] = s1<<13 | s1>>>19;
return (r >>> 0) / 4294967295; // 2^32-1
}
}
function xoroshiro64s(s) {
return function() {
var s0 = s[0], s1 = s[1];
var r = Math.imul(s0, 0x9E3779BB);
s1 ^= s0;
s[0] = (s0<<26 | s0>>>6) ^ s1 ^ (s1 << 9);
s[1] = s1<<13 | s1>>>19;
return (r >>> 0) / 4294967295; // 2^32-1
}
}
/*
xorshift128
----------------------
(Note: this is a continuation of xoshiro, so read its comments first.)
After implementing the brand new xoshiro, it seems that Marsaglia's original xorshift (2003) isn't too dissimilar,
so I decided to implement it as well. However keep in mind, it's supposedly inferior to xoshiro.
I included the 32-bit and 128-bit variants, but not the 'xorwow' variant. The 32-bit version is known to be weak, but
I find it interesting due to its high simplicity.
"The 128-bit algorithm passes the diehard tests. However, it fails the MatrixRank and LinearComp tests
of the BigCrush test suite from the TestU01 framework."
Used like so:
var rand = xorshift128([9**9, 8**9, 7**9, 6**9]); // needs some initial state/seed - use hash algorithm.
rand(); // returns 0.8493802803217854
rand(); // returns 0.9016569563890009
Note: xorshift128* and xorshift128+ by Vigna is entirely 64-bit and thus not compatible with JS.
*/
function xorshift128(s) {
return function() {
var z, t = s[3];
t ^= t << 11; t ^= t >>> 8;
s[3] = s[2]; s[2] = s[1];
z = s[1] = s[0];
t ^= z; t ^= z >>> 19;
s[0] = t;
return (t >>> 0) / 4294967295;
}
}
function xorshift32(s) {
return function() {
s ^= s << 13, s ^= s >>> 17, s ^= s << 5;
return (s >>> 0) / 4294967295;
}
}
/*
xoshiro128**
----------------------
A 32-bit PRNG by David Blackman and Sebastiano Vigna (May 2018)
It is related to xoroshiro128+ (2016) and xorshift128+ (2014) by the same authors.
Implemented from: http://xoshiro.di.unimi.it/xoshiro128starstar.c
This is supposedly the better variant (bettee than xoshiro128+).
Used like so:
var rand = xoshiro128ss([9**9, 8**9, 7**9, 6**9]); // needs some initial state/seed - use hash algorithm.
rand(); // returns 0.57136419438757
rand(); // returns 0.010435893665999174
*/
function xoshiro128ss(s) {
return function() {
var m = s[0] * 5, r = (m<<7 | m>>>25) * 9,
t = s[1] << 9;
s[2] ^= s[0], s[3] ^= s[1],
s[1] ^= s[2], s[0] ^= s[3],
s[2] ^= t, s[3] = s[3]<<11 | s[3]>>>21;
return (r >>> 0) / 4294967295; // 2^32-1
}
}
/*
xoshiro128+
----------------------
A 32-bit PRNG by David Blackman and Sebastiano Vigna (May 2018)
It is related to xoroshiro128+ (2016) and xorshift128+ (2014) by the same authors.
Implemented from: http://xoshiro.di.unimi.it/xoshiro128plus.c
It seems very simple yet supposedly passes BigCrush.
Possibly quite fast too.
Used like so:
var rand = xoshiro128p([9**9, 8**9, 7**9, 6**9]); // needs some initial state/seed - use hash algorithm.
rand(); // returns 0.3959026513621211
rand(); // returns 0.1824387749657035
*/
function xoshiro128p(s) {
return function() {
var r = s[0] + s[3], t = s[1] << 9;
s[2] ^= s[0], s[3] ^= s[1],
s[1] ^= s[2], s[0] ^= s[3],
s[2] ^= t, s[3] = s[3]<<11 | s[3]>>>21;
return (r >>> 0) / 4294967295; // 2^32-1
}
}
// just some old, incomplete LCG code that takes m,a,c arguments. Don't use this.
var LCG = function() {
var seed = 6;
return function(modulus, multiplier, increment) {
seed = (seed * multiplier + increment) % modulus;
return seed / modulus;
}
Copy link

ghost commented Dec 23, 2018

Note xoshiro128p claims to divide by 2^32-1 but it divides by 2^32, and Alea multiplies by 2^-32. Apart from the consistency/uniformity issues, personally I much prefer generators that return results in [0, 1) rather than [0, 1].

EDIT: actually Alea does not multiply by 2^-32 to get its output, it's Mash, my bad. But Alea returns n % 1 which is in [0, 1) too, so the same objection applies.

@bryc
Copy link
Author

bryc commented Feb 22, 2019

Note xoshiro128p claims to divide by 2^32-1 but it divides by 2^32, and Alea multiplies by 2^-32. Apart from the consistency/uniformity issues, personally I much prefer generators that return results in [0, 1) rather than [0, 1].

EDIT: actually Alea does not multiply by 2^-32 to get its output, it's Mash, my bad. But Alea returns n % 1 which is in [0, 1) too, so the same objection applies.

Fixed the inconsistency. This is all outdated code now though, I maintain a cleaner repo of PRNGs here.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment