hrandom.js

/*
 *   A C-program for MT19937, with initialization improved 2002/1/26.
 *   Coded by Takuji Nishimura and Makoto Matsumoto.
 *
 *   Before using, initialize the state by using init(seed)
 *   or init_by_array(init_key, key_length).
 *
 *   Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
 *   All rights reserved.
 *
 *   Redistribution and use in source and binary forms, with or without
 *   modification, are permitted provided that the following conditions
 *   are met:
 *
 *     1. Redistributions of source code must retain the above copyright
 *        notice, this list of conditions and the following disclaimer.
 *
 *     2. Redistributions in binary form must reproduce the above copyright
 *        notice, this list of conditions and the following disclaimer in the
 *        documentation and/or other materials provided with the distribution.
 *
 *     3. The names of its contributors may not be used to endorse or promote
 *        products derived from this software without specific prior written
 *        permission.
 *
 *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 *   A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 *   CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 *   EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 *   PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 *   PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 *   LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 *   NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 *   SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 *   Any feedback is very welcome.
 *   http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html
 *   email: m-mat @ math.sci.hiroshima-u.ac.jp (remove space)
 */

function Random (seed) {
  if (!seed) {
    seed = Date.now();
  }

  /* Period parameters */
  var N = 624, M = 397;
  var UPPER_MASK = 0x80000000; /* most significant w-r bits */
  var mt = new Array(N);   /* the array for the state vector  */
  var mtix = N+1;           /* mtix==N+1 means mt[N] is not initialized */

  /** Emulate 32-bit unsiged integers with overflow/underflow. Arguments (except for u32) must be uint32s. **/
  function u32 (n) {
    return n < 0 ? (n ^ UPPER_MASK) + UPPER_MASK : n;
  }

  function sub32 (n1, n2) {
    return n1 < n2 ? u32((0x100000000 - (n2 - n1)) & 0xffffffff) : n1 - n2;
  }

  function add32 (n1, n2) {
    return u32((n1 + n2) & 0xffffffff);
  }

  function mult32 (n1, n2) {
    var sum = 0;
    for (var i = 0; i < 32; ++i){
      if ((n1 >>> i) & 0x1){
        sum = add32(sum, u32(n2 << i));
      }
    }
    return sum;
  }

  /* initializes mt[N] with a seed */
  var init = function (seed) {
    mt[0]= u32(seed & 0xffffffff);
    for (mtix=1; mtix < N; mtix++) {
      mt[mtix] = add32(mult32(1812433253, u32(mt[mtix-1] ^ (mt[mtix-1] >>> 30))), mtix);
      mt[mtix] = u32(mt[mtix] & 0xffffffff);
    }
  };

  /* initialize by an array */
  var initByArray = function (init_key) {
    var i = 1, j = 0, k;
    init(19650218);
    for (k = (N > init_key.length ? N : init_key.length); k; k--) {
      mt[i] = add32(add32(u32(mt[i] ^ mult32(u32(mt[i-1] ^ (mt[i-1] >>> 30)), 1664525)), init_key[j]), j);
      mt[i] = u32(mt[i] & 0xffffffff);
      i++; j++;
      if (i >= N) {
        mt[0] = mt[N-1]; i=1;
      }
      if (j >= init_key.length) {
        j=0;
      }
    }
    for (k=N-1; k; k--) {
      mt[i] = sub32(u32((dbg=mt[i]) ^ mult32(u32(mt[i-1] ^ (mt[i-1] >>> 30)), 1566083941)), i);
      mt[i] = u32(mt[i] & 0xffffffff);
      i++;
      if (i >= N) {
        mt[0] = mt[N-1];
        i=1;
      }
    }
    mt[0] = 0x80000000; /* MSB is 1; assuring non-zero initial array */
  };

  /* generates a random number on [0,0xffffffff]-interval */
  var int32 = function () {
    var y, kk;
    var A = [0, 0x9908b0df];  /* constant vector a */
    var LOWER_MASK = 0x7fffffff; /* least significant r bits */

    if (mtix >= N) { /* generate N words at one time */
      for (kk=0; kk < (N-M); kk++) {
        y = u32((mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK));
        mt[kk] = u32(mt[kk+M] ^ (y >>> 1) ^ A[y & 0x1]);
      }
      for (; kk < (N-1) ; kk++) {
        y = u32((mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK));
        mt[kk] = u32(mt[kk+(M-N)] ^ (y >>> 1) ^ A[y & 0x1]);
      }

      y = u32((mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK));
      mt[N-1] = u32(mt[M-1] ^ (y >>> 1) ^ A[y & 0x1]);
      mtix = 0;
    }

    y = mt[mtix++];

    /* Tempering */
    y = u32(y ^ (y >>> 11));
    y = u32(y ^ ((y << 7) & 0x9d2c5680));
    y = u32(y ^ ((y << 15) & 0xefc60000));
    y = u32(y ^ (y >>> 18));

    return y;
  };

  /* generates a random number on [0,1)-real-interval */
  var real = function () {
    return int32() * (1.0/4294967296.0);
    /* divided by 2^32 */
  };

  /* generates a random number on [0,1) with 53-bit resolution*/
  var res53 = function () {
    var a=int32()>>>5, b=int32()>>>6;
    return(a*67108864.0+b) * (1.0/9007199254740992.0);
  };

  init(seed); /* Initialize the MT with the given seed. */

  return {
    next : function () {
      return real();
    },

    nextInt : function (max) {
      return Math.floor(real() * (max === undefined ? 4294967296 : max));
    },

    nextElement : function (array) {
      return array[this.nextInt(array.length)];
    },

    nextBoolean : function () {
      // Since 1.0 cannot be hit, this has a 50/50 split.
      return (real() >= 0.5);
    },

    shuffle : function (unshuffled) {
      var rand, shuffled = Object.create(Object.getPrototypeOf(unshuffled));

      unshuffled.forEach(function (value, ix) {
        if (ix === 0) {
          shuffled[0] = value;
        } else {
          rand = this.nextInt(ix + 1);
          shuffled[ix] = shuffled[rand];
          shuffled[rand] = value;
        }
      }, this);
      return shuffled;
    },

    // Copied from http://dtm.livejournal.com/38725.html
    shuffleInPlace : function shuffle(list) {
      var ix, jx, tmp;
      for (ix = 1; ix < list.length; ix++) {
	jx = this.nextInt(ix + 1);  // choose j in [0..i]
	if (jx != ix) {
    tmp = list[ix];           // swap list[i] and list[j]
    list[ix] = list[jx];
    list[jx] = tmp;
	}
      }

      return list;                  // meaningful return value.
    }
  };
}

module.exports = Random;