simple-squiggle

A restricted subset of Squiggle
Log | Files | Refs | README

xor4096.js (4559B)

      1 // A Javascript implementaion of Richard Brent's Xorgens xor4096 algorithm.
      2 //
      3 // This fast non-cryptographic random number generator is designed for
      4 // use in Monte-Carlo algorithms. It combines a long-period xorshift
      5 // generator with a Weyl generator, and it passes all common batteries
      6 // of stasticial tests for randomness while consuming only a few nanoseconds
      7 // for each prng generated.  For background on the generator, see Brent's
      8 // paper: "Some long-period random number generators using shifts and xors."
      9 // http://arxiv.org/pdf/1004.3115v1.pdf
     10 //
     11 // Usage:
     12 //
     13 // var xor4096 = require('xor4096');
     14 // random = xor4096(1);                        // Seed with int32 or string.
     15 // assert.equal(random(), 0.1520436450538547); // (0, 1) range, 53 bits.
     16 // assert.equal(random.int32(), 1806534897);   // signed int32, 32 bits.
     17 //
     18 // For nonzero numeric keys, this impelementation provides a sequence
     19 // identical to that by Brent's xorgens 3 implementaion in C.  This
     20 // implementation also provides for initalizing the generator with
     21 // string seeds, or for saving and restoring the state of the generator.
     22 //
     23 // On Chrome, this prng benchmarks about 2.1 times slower than
     24 // Javascript's built-in Math.random().
     25 
     26 (function(global, module, define) {
     27 
     28 function XorGen(seed) {
     29   var me = this;
     30 
     31   // Set up generator function.
     32   me.next = function() {
     33     var w = me.w,
     34         X = me.X, i = me.i, t, v;
     35     // Update Weyl generator.
     36     me.w = w = (w + 0x61c88647) | 0;
     37     // Update xor generator.
     38     v = X[(i + 34) & 127];
     39     t = X[i = ((i + 1) & 127)];
     40     v ^= v << 13;
     41     t ^= t << 17;
     42     v ^= v >>> 15;
     43     t ^= t >>> 12;
     44     // Update Xor generator array state.
     45     v = X[i] = v ^ t;
     46     me.i = i;
     47     // Result is the combination.
     48     return (v + (w ^ (w >>> 16))) | 0;
     49   };
     50 
     51   function init(me, seed) {
     52     var t, v, i, j, w, X = [], limit = 128;
     53     if (seed === (seed | 0)) {
     54       // Numeric seeds initialize v, which is used to generates X.
     55       v = seed;
     56       seed = null;
     57     } else {
     58       // String seeds are mixed into v and X one character at a time.
     59       seed = seed + '\0';
     60       v = 0;
     61       limit = Math.max(limit, seed.length);
     62     }
     63     // Initialize circular array and weyl value.
     64     for (i = 0, j = -32; j < limit; ++j) {
     65       // Put the unicode characters into the array, and shuffle them.
     66       if (seed) v ^= seed.charCodeAt((j + 32) % seed.length);
     67       // After 32 shuffles, take v as the starting w value.
     68       if (j === 0) w = v;
     69       v ^= v << 10;
     70       v ^= v >>> 15;
     71       v ^= v << 4;
     72       v ^= v >>> 13;
     73       if (j >= 0) {
     74         w = (w + 0x61c88647) | 0;     // Weyl.
     75         t = (X[j & 127] ^= (v + w));  // Combine xor and weyl to init array.
     76         i = (0 == t) ? i + 1 : 0;     // Count zeroes.
     77       }
     78     }
     79     // We have detected all zeroes; make the key nonzero.
     80     if (i >= 128) {
     81       X[(seed && seed.length || 0) & 127] = -1;
     82     }
     83     // Run the generator 512 times to further mix the state before using it.
     84     // Factoring this as a function slows the main generator, so it is just
     85     // unrolled here.  The weyl generator is not advanced while warming up.
     86     i = 127;
     87     for (j = 4 * 128; j > 0; --j) {
     88       v = X[(i + 34) & 127];
     89       t = X[i = ((i + 1) & 127)];
     90       v ^= v << 13;
     91       t ^= t << 17;
     92       v ^= v >>> 15;
     93       t ^= t >>> 12;
     94       X[i] = v ^ t;
     95     }
     96     // Storing state as object members is faster than using closure variables.
     97     me.w = w;
     98     me.X = X;
     99     me.i = i;
    100   }
    101 
    102   init(me, seed);
    103 }
    104 
    105 function copy(f, t) {
    106   t.i = f.i;
    107   t.w = f.w;
    108   t.X = f.X.slice();
    109   return t;
    110 };
    111 
    112 function impl(seed, opts) {
    113   if (seed == null) seed = +(new Date);
    114   var xg = new XorGen(seed),
    115       state = opts && opts.state,
    116       prng = function() { return (xg.next() >>> 0) / 0x100000000; };
    117   prng.double = function() {
    118     do {
    119       var top = xg.next() >>> 11,
    120           bot = (xg.next() >>> 0) / 0x100000000,
    121           result = (top + bot) / (1 << 21);
    122     } while (result === 0);
    123     return result;
    124   };
    125   prng.int32 = xg.next;
    126   prng.quick = prng;
    127   if (state) {
    128     if (state.X) copy(state, xg);
    129     prng.state = function() { return copy(xg, {}); }
    130   }
    131   return prng;
    132 }
    133 
    134 if (module && module.exports) {
    135   module.exports = impl;
    136 } else if (define && define.amd) {
    137   define(function() { return impl; });
    138 } else {
    139   this.xor4096 = impl;
    140 }
    141 
    142 })(
    143   this,                                     // window object or global
    144   (typeof module) == 'object' && module,    // present in node.js
    145   (typeof define) == 'function' && define   // present with an AMD loader
    146 );