Skip to content

Instantly share code, notes, and snippets.

@need12648430
Last active Aug 29, 2015
Embed
What would you like to do?
Linear congruential generator (Seedable PRNG) with weighted choices and shuffling in 1.4kb of clean JS.
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[0])
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)[0])
);
return out;
}
};
return LCG;
})();
@funny-falcon
Copy link

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).

Read more here http://en.wikipedia.org/wiki/Linear_congruential_generator#Period_length

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)

https://en.wikipedia.org/wiki/IEEE_floating_point
https://en.wikipedia.org/wiki/Double-precision_floating-point_format

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

Loading

@funny-falcon
Copy link

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 %.

Loading

@need12648430
Copy link
Author

need12648430 commented May 8, 2015

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

Loading

@sbrl
Copy link

sbrl commented May 25, 2015

This looks really cool. Definitely going to star this for use in a future project.

Loading

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