{{ message }}

Instantly share code, notes, and snippets.

# need12648430/lcg.js

Last active Aug 29, 2015
Linear congruential generator (Seedable PRNG) with weighted choices and shuffling in 1.4kb of clean JS.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 var LCG = (function () { var c = 0x93456789, a = 0x169659, mod, mask, r; mask = (mod = Math.pow(2, 31)) - 1; function LCG(seed) { this.seed = seed || new Date().getTime(); } LCG.prototype = { nextInt: function () { r = this.seed + c; this.seed = (this.seed * a + c) & mask; r = ((r ^ (r >>> 16)) * a) & mask; return r ^ (r >>> 16); }, nextFloat: function () {return this.nextInt() / mod}, rangeInt: function (start, end) { var n; while ((n = this.nextInt()) > mod - mod % (end - start)) ; return start + n % (end - start); }, rangeFloat: function (start, end) {return start + this.nextFloat() * (end - start);}, choose: function (set, weights) { if (!weights) return set[LCG.prototype.rangeInt(0, set.length)]; if (set.length != weights.length) throw "Set length must match weights length."; var i, t, s, a; for (t = i = 0; i < set.length; t += weights[i ++]); s = this.rangeFloat(0, t); for (i = a = 0; a < t; a += weights.shift(i ++)) if (s >= a && s < a + weights) return set[i]; }, shuffle: function (set) { for ( var copy = set.slice(0), out = []; copy.length > 0; out.push(copy.splice(this.nextInt() % copy.length, 1)) ); return out; } }; return LCG; })();

### funny-falcon commented May 8, 2015

Why not use 2^n module? then you will have full 2^n period instead of 1073741789 / 2 (cause LCG with prime number has half period).

More over,

``````> Math.log(679186565 * (1073741788 + 921746065)) / Math.log(2)
60.233327031140036
``````

You run out of double precision (javascript numbers has only 53 bits in mantisa cause they are IEEE754 doubles)

So that, you generator has really unpredictable period.

I'll recomend you to use parameters like this:

```/* this value are arbitrary,
they just satisfy conditions for full period LCG for 2^31 period
and do not overflow double precision (53 bits) */
/* we could have only 2 ^ 31 period cause javascript has only signed integers */
var c = 0x93456789; /* c % 2 != 0 && c < Math.pow(2, 53) */
var a = 0x169659;       /* (a-1)%4 == 0 && a < Math.pow(2, 21)  where 21 < 53 - 31 */
var mod = Math.pow(2, 31); /* ((mod-1)*a + c) < Math.pow(2, 53) */
this.seed = (this.seed*a + c) % mod;```

`a` and `c` could be other that satisfy conditions in comments

### funny-falcon commented May 8, 2015

2^n generator has a flaw with lower bits, which have a smaller period.
This could be fixed by additional shuffling:

```var c = 0x93456789;
var a = 0x169659;
var mod = Math.pow(2, 31);
var mask = mod - 1;
LCG.prototype = {
nextInt:
function () {
var res = this.seed + c; /* it is a bit faster to set value before modification */
this.seed = (this.seed * a + c) & mask; /* using & instead of % is much faster */
res = ((res ^ (res >>> 16)) * a) & mask;
return res ^ (res >>> 16);
}```

Even with this additional shuffling, nodejs runs this faster than original code, cause `&` used instead of `%`.

### need12648430 commented May 8, 2015

Should have done some more studying before attempting this. Maybe looked at some existing implementations - but thank you.