bryc
12/1/2017 - 7:16 AM
PRNGs
PRNGs
// just some old, incomplete LCG code that takes m,a,c arguments. Don't use this.
var seed = 6;
var LCG = function() {
var seed = 6;
return function(modulus, multiplier, increment) {
seed = (seed * multiplier + increment) % modulus;
return seed / modulus;
}
var Random = function(seed) {
this.seed = seed;
}/*
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) / 4294967296; // 2^32-1
}
}
/* initseed
----------------------
xoshiro family of PRNGs typically require a well-distributed state to start with.
So this is just an example way of hashing the input data properly.
It uses fmix32 from MurmurHash3.
This reliance on another function shouldn't hurt the performance of the PRNG. However a fast hash function should be chosen.
Used like so:
var rand = xoshiro128ss( initseed([1, 2, 3, 4]) );
*/
function initseed(s) {
function mix(h) {
h ^= h>>>16; h = Math.imul(h,2246822507);
h ^= h>>>13; h = Math.imul(h,3266489909); h ^= h>>>16;
return h;
}
var e = s[0] + s[1] + s[2] + s[3];
s[0] += e ^ 597399067; s[1] ^= e ^ 668265263; s[2] += e ^ 951274213; s[3] ^= e ^ 374761393;
s[0] = mix(s[0]) + s[1]; s[1] = mix(s[1]);
s[2] = mix(s[2]) + s[3]; s[3] = mix(s[3]);
e = s[0] + s[1] + s[2] + s[3];
s[0] += e; s[1] ^= e; s[2] += e; s[3] ^= e;
return s;
}/*
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;
}
}/*
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
}
}/*
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
}/*
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;
}/*
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);
};
}();
}