20
\$\begingroup\$

The following is an implementation of the Alea random number generation approach by Johannes Baagøe, reworked from the rot.js implementation by dropping all the pesky underscore prefixes in the variables and making those variables truly private.

The code has passed through JsHint and js-beautify, please address any and all aspects. The alea object is intended to be used as a singleton.

alea = function Alea() {
  //2^-32
  var frac = 2.3283064365386963e-10,
    states = [],
    s0, s1, s2, c;

  /*jshint -W004 */
  function seed( seed ) {
    s0 = ( ( seed || new Date().getTime() ) >>> 0 ) * frac;
    s1 = ( seed = ( seed * 69069 + 1 ) >>> 0 ) * frac;
    s2 = ( seed = ( seed * 69069 + 1 ) >>> 0 ) * frac;
    c = 1;
    return this;
  }

  function random() {
    var t = 2091639 * s0 + c * frac;
    s0 = s1;
    s1 = s2;
    c = t | 0;
    s2 = t - c;
    return s2;
  }

  function normal( mean, stddev ) {
    var u, v, r;
    do {
      u = 2 * random() - 1;
      v = 2 * random() - 1;
      r = u * u + v * v;
    } while ( r > 1 || !r );
    var gauss = u * Math.sqrt( -2 * Math.log( r ) / r );
    return( mean || 0 ) + gauss * ( stddev || 1 );
  }

  function percentage() {
    return 1 + Math.floor( random() * 100 );
  }

  function pushState() {
    states.push( [ s0, s1, s2, c ] );
  }

  function popState() {
      if( states.length ) {
        var state = states.pop();
        s0 = state[ 0 ];
        s1 = state[ 1 ];
        s2 = state[ 2 ];
        c = state[ 3 ];
      }
    }
    //Take care of the initial (mystery meat) seed
  seed( 3717022350 );
  //Return the module
  return {
    seed: seed,
    random: random,
    normal: normal,
    percentage: percentage,
    popState: popState,
    pushState: pushState,
  };
}();

Some research:

  • The original site went down, but there is the wayback machine:
  • There is an implementation very close to the original here:
  • There is an implementation also in rot.js.
\$\endgroup\$
  • \$\begingroup\$ Could you add some links to "canonical"/original implementations? Just to compare and contrast \$\endgroup\$ – Flambino Dec 5 '14 at 4:13
  • \$\begingroup\$ Done, especially the wayback link is worth reading. \$\endgroup\$ – konijn Dec 5 '14 at 13:44
9
+150
\$\begingroup\$

This is decidedly not my area of expertise so I've focussed on "the easy parts": Style and API.

But I think I've found a bug in the seed function:

If called without any arguments (or a falsey argument), the following happens:

// s0 is defined using a fallback/default value for `seed`
s0 = ( ( seed || new Date().getTime() ) >>> 0 ) * frac;

// but said fallback isn't stored, so the following *always* equates to:
//   s1 = (seed = 1) * frac  =>  s1 = frac;
s1 = ( seed = ( seed * 69069 + 1 ) >>> 0 ) * frac;

// and thus this *always* equates to:
//   s2 = (seed = 69070) * frac  =>  s2 = frac * 69070;
s2 = ( seed = ( seed * 69069 + 1 ) >>> 0 ) * frac;

Again, I don't dare speculate what impact this has on the overall randomness. The behavior's consistent though, so everything still works. But I assume it isn't quite as it should be, as you've basically got 2 seed values.

I'd propose unpacking some of those lines:

function seed(seed) {
  seed = (seed || new Date().getTime()) >>> 0;
  s0 = seed * frac;

  seed = (seed * 69069 + 1) >>> 0;
  s1 = seed * frac;

  seed = (seed * 69069 + 1) >>> 0;
  s2 = seed * frac;

  c = 1;
  return this;
}

There's certainly some repetition there, but it seems clearer to me. I've also changed the use a whitespace a little (particularly inside parentheses), but that's just personal preference.

Speaking of falsey arguments, it'd be nice to accept zero as a valid seed, without defaulting to the current time (numeric zero seems like a valid enough seed value, if a little unimaginative). One could for instance do;

seed = (typeof seed === 'number' ? seed : Date.now()) >>> 0;

The use of Date.now() is of course predicated on the runtimes you're targeting. I mostly used it to save some letters here.

Edit: Forgot this, but the above line won't work as intended if seed is NaN, since typeof NaN === 'number'... yes, it's bizarre. Anyway, an isNaN() check might be useful.

From here on it's mostly readability suggestions and such:

You've named the wrapper function Alea although it's not really a constructor and could just be an anonymous IIFE. I'd probably just do the latter.

frac should perhaps be named FRAC as it's treated as constant (even if it isn't actually constant). I can't describe it better than "fraction" or I might suggest a different name altogether.

In random() you've got a magic number in the form of 2091639. I'd suggest sticking that in a variable, just to label it. If of course there's a good label to give it other than "a number". Same goes for the 69069 in seed.

I'd also move the assignment of c up a bit just have nicely aligned s0, s1, s2 lines:

function random() {
  var t = 2091639 * s0 + c * frac;
  c = t | 0;      
  s0 = s1;
  s1 = s2;
  s2 = t - c;
  return s2;
}

Aaah... Ok, yeah, that's really OCD'ish :)

Speaking of OCD: The whitespace in normal() irks me a little. The return(... line especially, makes return look like a function invocation. Again, personal preference; I just think it looks odd.

percentage() seems incapable of returning zero. Any reason to not use Math.round() instead of floor + 1? (Also interesting that you've previously used the | 0 trick instead of spelling out Math.floor.)

And there's this line:

//Take care of the initial (mystery meat) seed
seed( 3717022350 );

Wouldn't it be more natural to let seed default to the current time? It'd let the generator be "more random" out of the box, without requiring the user to explicitly call seed as the first thing.

By the way, it might be nice to add a function to return the seed value. Whether it's the fixed number above or the current time, it could be nice to be able to extract the seed value, if you haven't set it yourself.

Lastly, while I like the pushState/popState way of managing the generator, it introduces some complexity in usage, I think.

For instance, calling pushState does nothing on its own; you still have to call seed separately. Meanwhile popState may fail silently. Being a singleton, there could also be some confusion about whether to push a state or just reseed the generator's current state. It's impossible for a piece of code to know if some other code has reseeded or pushed a new state, so you might end up with some belt-and-suspenders code to always push a state, reseed to a known value, do stuff, and pop state again if the generator is used in several places.

pushState() and popState() might at least return this, to allow some simple chaining, like seed() does. Or simply make a pushSeed function, which sounds lurid, but you can just say it's an homage to The Roots' 2002 hit...

On the whole though, I'd probably prefer a non-singleton implementation where "state" is simply a generator instance. Each instance could still have a state-stack of course.

Here's a light refactoring, which'll return an object (regardless of whether you call new Alea() or just Alea()). I've left out the push/pop state stuff, but again, you could keep that in there. I've added a getSeed function, just as an example.

function Alea(initialSeed) {
  var FRAC = 2.3283064365386963e-10, // 2^-32
      T = 2091639,
      states = [],
      seedValue,
      s0, s1, s2, c;

  function seed(seed) {
    seedValue = (seed || new Date().getTime()) >>> 0;
    seed = seedValue;
    s0 = seed * FRAC;
    seed = (seed * 69069 + 1) >>> 0;
    s1 = seed * FRAC;
    seed = (seed * 69069 + 1) >>> 0;
    s2 = seed * FRAC;
    c = 1;
    return this;
  }

  function getSeed() {
    return seedValue;
  }

  function random() {
    var t = T * s0 + c * FRAC;
    c = t | 0;
    s0 = s1;
    s1 = s2;
    s2 = t - c;
    return s2;
  }

  function normal(mean, stddev) {
    var u, v, r, gauss;
    do {
      u = 2 * random() - 1;
      v = 2 * random() - 1;
      r = u * u + v * v;
    } while ( r > 1 || !r );

    gauss = u * Math.sqrt(-2 * Math.log(r) / r);

    return (mean || 0) + gauss * (stddev || 1);
  }

  function percentage() {
    return Math.round(random() * 100);
  }

  // Seed this "instance"
  seed(initialSeed);

  // Return an object
  return {
    seed: seed,
    random: random,
    normal: normal,
    percentage: percentage,
    getSeed: getSeed
  };
}
\$\endgroup\$
  • \$\begingroup\$ I can't believe I noticed your great answer 3 years after... My apologies! \$\endgroup\$ – konijn Jun 29 '18 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.