-
-
Save bryc/38a86416e8fa940e009adb15821f36d7 to your computer and use it in GitHub Desktop.
| /* | |
| 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[1] * 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; | |
| } | |
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.
Presented xoshiro128ss implementation is based on 1.0 which has a major bug.
Here is updated C code: https://xoshiro.di.unimi.it/xoshiro128starstar.c
Note that version 1.0 had mistakenly s[0] instead of s[1] as state word passed to the scrambler.
Correct implementation:
function xoshiro128ss(s) {
return function() {
var m = s[1] * 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
}
}@rinart73 fixed, though this gist is obsolete - see https://github.com/bryc/code/blob/master/jshash/PRNGs.md
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.