Bug 872352 - Add NBody to parjs-benchmarks. (r=nmatsakis) DONTBUILD
authorShu-yu Guo <shu@rfrn.org>
Tue, 14 May 2013 19:23:20 -0700
changeset 143443 04155dec2ead2dbc7bc13192d200785213d2476b
parent 143442 1d3b60ab634a346cd61e288ec6b9a6629552f539
child 143444 4667ec13bb63766ee8c694e801491d10949c209a
push id2697
push userbbajaj@mozilla.com
push dateMon, 05 Aug 2013 18:49:53 +0000
treeherdermozilla-beta@dfec938c7b63 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnmatsakis
bugs872352
milestone24.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 872352 - Add NBody to parjs-benchmarks. (r=nmatsakis) DONTBUILD
js/src/parjs-benchmarks/nbody-seeded.js
js/src/parjs-benchmarks/seedrandom.js
new file mode 100644
--- /dev/null
+++ b/js/src/parjs-benchmarks/nbody-seeded.js
@@ -0,0 +1,554 @@
+//
+// NBody adapted from Intel's nbody benchmark.
+//
+
+load(libdir + "util.js");
+load(libdir + "seedrandom.js");
+
+var NBody = {
+  Constant: {
+    "deltaTime": 1,     // 0.005 in their code.
+    "epsSqr": 50,       // softening factor, when they compute, set to 50.
+    "initialVelocity": 8 // set to 0 to turn off
+  },
+
+  init: function init(mode, numBodies) {
+    var initPos = new Array(numBodies);
+    var initVel = new Array(numBodies);
+
+    // initialization of inputs
+    for (var i = 0; i < numBodies; i++) {
+      // [x,y,z]
+      initPos[i] = [Math.floor((Math.random()) * 40000),
+                    Math.floor((Math.random()) * 20000),
+                    Math.floor((Math.random() - .25) * 50000)];
+
+      // [x,y,z,x,y,z]
+      initVel[i] = [(Math.random() - 0.5) * NBody.Constant.initialVelocity,
+                    (Math.random() - 0.5) * NBody.Constant.initialVelocity,
+                    (Math.random()) * NBody.Constant.initialVelocity + 10,
+
+                    (Math.random() - 0.5) * NBody.Constant.initialVelocity,
+                    (Math.random() - 0.5) * NBody.Constant.initialVelocity,
+                    (Math.random()) * NBody.Constant.initialVelocity];
+    }
+
+    NBody.private = {};
+
+    if (mode === "par") {
+      NBody.private.pos = new ParallelArray(initPos);
+      NBody.private.vel = new ParallelArray(initVel);
+    } else {
+      NBody.private.pos = initPos;
+      NBody.private.vel = initVel;
+    }
+
+    NBody.numBodies = numBodies;
+    NBody.time = 0;
+  },
+
+  // Parallel
+
+  tickPar: function tickPar() {
+    NBody.private.vel = new ParallelArray([NBody.numBodies], NBody.velocityPar);
+    NBody.private.pos = new ParallelArray([NBody.numBodies], NBody.positionPar);
+    NBody.time++;
+  },
+
+  velocityPar: function velocityPar(index) {
+    var pos = NBody.private.pos;
+    var vel = NBody.private.vel;
+
+    var deltaTime = NBody.Constant.deltaTime;
+    var epsSqr = NBody.Constant.epsSqr;
+    var time = NBody.time;
+
+    var shape = vel.shape[0];
+
+    var newVel;
+    var newX, newY, newZ;
+    var newX2, newY2, newZ2;
+
+    var cX = Math.cos(time / 22) * -4200;
+    var cY = Math.sin(time / 14) * 9200;
+    var cZ = Math.sin(time / 27) * 6000;
+
+    // pull to center
+    var maxDistance = 3400;
+    var pullStrength = .042;
+
+    var speedLimit = 8;
+
+    // zones
+    var zone = 400;
+    var repel = 100;
+    var align = 300;
+    var attract = 100;
+
+    if (time < 500) {
+      speedLimit = 2000;
+      var attractPower = 100.9;
+    } else {
+      speedLimit = .2;
+      attractPower = 20.9;
+    }
+
+    var zoneSqrd = zone * zone + zone * zone + zone * zone;
+
+    var accX = 0, accY = 0, accZ = 0;
+    var accX2 = 0, accY2 = 0, accZ2 = 0;
+    var i;
+
+    // define particle 1 center distance
+    var dirToCenterX = cX - pos.get(index)[0];
+    var dirToCenterY = cY - pos.get(index)[1];
+    var dirToCenterZ = cZ - pos.get(index)[2];
+
+    var distanceSquaredTo = dirToCenterX * dirToCenterX + dirToCenterY * dirToCenterY + dirToCenterZ * dirToCenterZ;
+    var distToCenter = Math.sqrt(distanceSquaredTo);
+
+    // orient to center
+    if (distToCenter > maxDistance) {
+      var velc = (distToCenter - maxDistance) * pullStrength;
+      if (time < 200)
+        velc = .2;
+      else velc = (distToCenter - maxDistance) * pullStrength;
+
+      accX += (dirToCenterX / distToCenter) * velc;
+      accY += (dirToCenterY / distToCenter) * velc;
+      accZ += (dirToCenterZ / distToCenter) * velc;
+    }
+
+    for (i = 0; i < shape; i = i + 1) {
+      var rx = pos.get(i)[0] - pos.get(index)[0];
+      var ry = pos.get(i)[1] - pos.get(index)[1];
+      var rz = pos.get(i)[2] - pos.get(index)[2];
+
+      // make sure we are not testing the particle against its own position
+      var areSame = 0;
+      if (pos.get(i)[0] == pos.get(index)[0] && pos.get(i)[1] == pos.get(index)[1] && pos.get(i)[2] == pos.get(index)[2])
+        areSame += 1;
+
+      var distSqrd = rx * rx + ry * ry + rz * rz;
+
+      // cant use eqals to test, only <= or >= WTF
+      if (distSqrd < zoneSqrd && areSame <= 0) {
+        var length = Math.sqrt(distSqrd);
+        var percent = distSqrd / zoneSqrd;
+
+        if (distSqrd < repel) {
+          var F = (repel / percent - 1) * .025;
+
+          var normalRx = (rx / length) * F;
+          var normalRy = (ry / length) * F;
+          var normalRz = (rz / length) * F;
+
+          accX = accX + normalRx;
+          accY = accY + normalRy;
+          accZ = accZ + normalRz;
+
+          accX2 = accX2 - normalRx;
+          accY2 = accY2 - normalRy;
+          accZ2 = accZ2 - normalRz;
+        } else if (distSqrd < align) { //align
+          var threshDelta = align - repel;
+          var adjustedPercent = (percent - repel) / threshDelta;
+          var Q = (.5 - Math.cos(adjustedPercent * 3.14159265 * 2) * .5 + .5) * 100.9;
+
+          // get velocity 2
+          var velX2 = vel.get(i)[4];
+          var velY2 = vel.get(i)[5];
+          var velZ2 = vel.get(i)[6];
+
+          var velLength2 = Math.sqrt(velX2 * velX2 + velY2 * velY2 + velZ2 * velZ2);
+
+          // normalize vel2 and multiply by factor
+          velX2 = (velX2 / velLength2) * Q;
+          velY2 = (velY2 / velLength2) * Q;
+          velZ2 = (velZ2 / velLength2) * Q;
+
+          // get own velocity
+          var velX = vel.get(i)[0];
+          var velY = vel.get(i)[1];
+          var velZ = vel.get(i)[2];
+
+          var velLength = Math.sqrt(velX * velX + velY * velY + velZ * velZ);
+
+          // normalize own velocity
+          velX = (velX / velLength) * Q;
+          velY = (velY / velLength) * Q;
+          velZ = (velZ / velLength) * Q;
+
+          accX += velX2;
+          accY += velY2;
+          accZ += velZ2;
+
+          accX2 += velX;
+          accY2 += velY;
+          accZ2 += velZ;
+        }
+
+        if (distSqrd > attract) { // attract
+          var threshDelta2 = 1 - attract;
+          var adjustedPercent2 = (percent - attract) / threshDelta2;
+          var C = (1 - (Math.cos(adjustedPercent2 * 3.14159265 * 2) * 0.5 + 0.5)) * attractPower;
+
+          // normalize the distance vector
+          var dx = (rx / (length)) * C;
+          var dy = (ry / (length)) * C;
+          var dz = (rz / (length)) * C;
+
+          accX += dx;
+          accY += dy;
+          accZ += dz;
+
+          accX2 -= dx;
+          accY2 -= dy;
+          accZ2 -= dz;
+        }
+      }
+    }
+
+    // Speed limits
+    if (time > 500) {
+      var accSquared = accX * accX + accY * accY + accZ * accZ;
+      if (accSquared > speedLimit) {
+        accX = accX * .015;
+        accY = accY * .015;
+        accZ = accZ * .015;
+      }
+
+      var accSquared2 = accX2 * accX2 + accY2 * accY2 + accZ2 * accZ2;
+      if (accSquared2 > speedLimit) {
+        accX2 = accX2 * .015;
+        accY2 = accY2 * .015;
+        accZ2 = accZ2 * .015;
+      }
+    }
+
+    // Caclulate new velocity
+    newX = (vel.get(index)[0]) + accX;
+    newY = (vel.get(index)[1]) + accY;
+    newZ = (vel.get(index)[2]) + accZ;
+
+    newX2 = (vel.get(index)[3]) + accX2;
+    newY2 = (vel.get(index)[4]) + accY2;
+    newZ2 = (vel.get(index)[5]) + accZ2;
+
+    if (time < 500) {
+      var acs = newX2 * newX2 + newY2 * newY2 + newZ2 * newZ2;
+      if (acs > speedLimit) {
+        newX2 = newX2 * .15;
+        newY2 = newY2 * .15;
+        newZ2 = newZ2 * .15;
+      }
+
+      var acs2 = newX * newX + newY * newY + newZ * newZ;
+      if (acs2 > speedLimit) {
+        newX = newX * .15;
+        newY = newY * .15;
+        newZ = newZ * .15;
+      }
+    }
+
+    return [newX, newY, newZ, newX2, newY2, newZ2];
+  },
+
+  positionPar: function positionPar(index) {
+    var vel = NBody.private.vel;
+    var pos = NBody.private.pos;
+
+    var x = 0;
+    var y = 0;
+    var z = 0;
+
+    var velX = vel.get(index)[0];
+    var velY = vel.get(index)[1];
+    var velZ = vel.get(index)[2];
+
+    var velX2 = vel.get(index)[3];
+    var velY2 = vel.get(index)[4];
+    var velZ2 = vel.get(index)[5];
+
+    var netVelX = (velX - velX2);
+    var netVelY = (velY - velY2);
+    var netVelZ = (velZ - velZ2);
+
+    x = pos.get(index)[0] + (netVelX);
+    y = pos.get(index)[1] + (netVelY);
+    z = pos.get(index)[2] + (netVelZ);
+
+    return [x, y, z];
+  },
+
+  // Sequential
+
+  tickSeq: function tickSeq() {
+    var numBodies = NBody.numBodies;
+    var newVel = new Array(numBodies);
+    var newPos = new Array(numBodies);
+
+    for (var i = 0; i < numBodies; i++)
+      newVel[i] = NBody.velocitySeq(i);
+
+    for (var i = 0; i < numBodies; i++)
+      newPos[i] = NBody.positionSeq(i);
+
+    NBody.private.vel = newVel;
+    NBody.private.pos = newPos;
+
+    NBody.time++;
+  },
+
+  velocitySeq: function velocitySeq(index) {
+    var vel = NBody.private.vel;
+    var pos = NBody.private.pos;
+
+    var deltaTime = NBody.Constant.deltaTime;
+    var epsSqr = NBody.Constant.epsSqr;
+    var time = NBody.time;
+
+    var shape = pos.length;
+
+    var newVel;
+    var newX, newY, newZ;
+    var newX2, newY2, newZ2;
+
+    var cX = Math.cos(time / 22) * -4200;
+    var cY = Math.sin(time / 14) * 9200;
+    var cZ = Math.sin(time / 27) * 6000;
+
+    // pull to center
+    var maxDistance = 3400;
+    var pullStrength = .042;
+
+    var speedLimit = 8;
+
+    // zones
+    var zone = 400;
+    var repel = 100;
+    var align = 300;
+    var attract = 100;
+
+
+    if (time < 500) {
+      speedLimit = 2000;
+      var attractPower = 100.9;
+    } else {
+      speedLimit = .2;
+      attractPower = 20.9;
+    }
+
+    var zoneSqrd = zone * zone + zone * zone + zone * zone;
+
+    var accX = 0, accY = 0, accZ = 0;
+    var accX2 = 0, accY2 = 0, accZ2 = 0;
+    var i;
+
+    // define particle 1 center distance
+    var dirToCenterX = cX - pos[index][0];
+    var dirToCenterY = cY - pos[index][1];
+    var dirToCenterZ = cZ - pos[index][2];
+
+    var distanceSquaredTo = dirToCenterX * dirToCenterX + dirToCenterY * dirToCenterY + dirToCenterZ * dirToCenterZ;
+    var distToCenter = Math.sqrt(distanceSquaredTo);
+
+    // orient to center
+    if (distToCenter > maxDistance) {
+      var velc = (distToCenter - maxDistance) * pullStrength;
+      if (time < 200)
+        velc = .2;
+      else velc = (distToCenter - maxDistance) * pullStrength;
+
+      accX += (dirToCenterX / distToCenter) * velc;
+      accY += (dirToCenterY / distToCenter) * velc;
+      accZ += (dirToCenterZ / distToCenter) * velc;
+    }
+
+    for (i = 0; i < shape; i = i + 1) {
+      var rx = pos[i][0] - pos[index][0];
+      var ry = pos[i][1] - pos[index][1];
+      var rz = pos[i][2] - pos[index][2];
+
+      var areSame = 0;
+      if (pos[i][0] == pos[index][0] && pos[i][1] == pos[index][1] && pos[i][2] == pos[index][2])
+        areSame += 1;
+
+      var distSqrd = rx * rx + ry * ry + rz * rz;
+
+      // cant use eqals to test, only <= or >= WTF
+      if (distSqrd < zoneSqrd && areSame <= 0) {
+        var length = Math.sqrt(distSqrd);
+        var percent = distSqrd / zoneSqrd;
+
+
+        if (distSqrd < repel) {
+          var F = (repel / percent - 1) * .025;
+
+          var normalRx = (rx / length) * F;
+          var normalRy = (ry / length) * F;
+          var normalRz = (rz / length) * F;
+
+          accX = accX + normalRx;
+          accY = accY + normalRy;
+          accZ = accZ + normalRz;
+
+          accX2 = accX2 - normalRx;
+          accY2 = accY2 - normalRy;
+          accZ2 = accZ2 - normalRz;
+        } else if (distSqrd < align) { //align
+          var threshDelta = align - repel;
+          var adjustedPercent = (percent - repel) / threshDelta;
+          var Q = (.5 - Math.cos(adjustedPercent * 3.14159265 * 2) * .5 + .5) * 100;
+
+          // get velocity 2
+          var velX2 = vel[i][3];
+          var velY2 = vel[i][4];
+          var velZ2 = vel[i][5];
+
+          var velLength2 = Math.sqrt(velX2 * velX2 + velY2 * velY2 + velZ2 * velZ2);
+
+          // normalize vel2 and multiply by factor
+          velX2 = (velX2 / velLength2) * Q;
+          velY2 = (velY2 / velLength2) * Q;
+          velZ2 = (velZ2 / velLength2) * Q;
+
+          // get own velocity
+          var velX = vel[i][0];
+          var velY = vel[i][1];
+          var velZ = vel[i][2];
+
+          var velLength = Math.sqrt(velX * velX + velY * velY + velZ * velZ);
+
+          // normalize own velocity
+          velX = (velX / velLength) * Q;
+          velY = (velY / velLength) * Q;
+          velZ = (velZ / velLength) * Q;
+
+          accX += velX2;
+          accY += velY2;
+          accZ += velZ2;
+
+          accX2 += velX;
+          accY2 += velY;
+          accZ2 += velZ;
+        }
+
+        if (distSqrd > attract) {        //attract
+          var threshDelta2 = 1 - align;
+          var adjustedPercent2 = (percent - align) / threshDelta2;
+          var C = (1 - (Math.cos(adjustedPercent2 * 3.14159265 * 2) * 0.5 + 0.5)) * attractPower;
+
+          // normalize the distance vector
+          var dx = (rx / (length)) * C;
+          var dy = (ry / (length)) * C;
+          var dz = (rz / (length)) * C;
+
+          debug = 1.1;
+
+          accX += dx;
+          accY += dy;
+          accZ += dz;
+
+          accX2 -= dx;
+          accY2 -= dy;
+          accZ2 -= dz;
+        }
+      }
+    }
+
+    // enforce speed limits
+    if (time > 500) {
+      var accSquared = accX * accX + accY * accY + accZ * accZ;
+      if (accSquared > speedLimit) {
+        accX = accX * .015;
+        accY = accY * .015;
+        accZ = accZ * .015;
+      }
+
+      var accSquared2 = accX2 * accX2 + accY2 * accY2 + accZ2 * accZ2;
+      if (accSquared2 > speedLimit) {
+        accX2 = accX2 * .015;
+        accY2 = accY2 * .015;
+        accZ2 = accZ2 * .015;
+      }
+    }
+
+    // Caclulate new velocity
+    newX = vel[index][0] + accX;
+    newY = vel[index][1] + accY;
+    newZ = vel[index][2] + accZ;
+
+    newX2 = vel[index][3] + accX2;
+    newY2 = vel[index][4] + accY2;
+    newZ2 = vel[index][5] + accZ2;
+
+    if (time < 500) {
+      var acs = newX2 * newX2 + newY2 * newY2 + newZ2 * newZ2;
+      if (acs > speedLimit) {
+        newX2 = newX2 * .15;
+        newY2 = newY2 * .15;
+        newZ2 = newZ2 * .15;
+      }
+
+      var acs2 = newX * newX + newY * newY + newZ * newZ;
+      if (acs2 > speedLimit) {
+        newX = newX * .15;
+        newY = newY * .15;
+        newZ = newZ * .15;
+      }
+    }
+
+    return [newX, newY, newZ, newX2, newY2, newZ2];
+  },
+
+  positionSeq: function positionSeq(index) {
+    var vel = NBody.private.vel;
+    var pos = NBody.private.pos;
+
+    var x = 0;
+    var y = 0;
+    var z = 0;
+
+    var velX = vel[index][0];
+    var velY = vel[index][1];
+    var velZ = vel[index][2];
+
+    var velX2 = vel[index][3];
+    var velY2 = vel[index][4];
+    var velZ2 = vel[index][5];
+
+    var netX = (velX - velX2);
+    var netY = (velY - velY2);
+    var netZ = (velZ - velZ2);
+
+    x = pos[index][0] + netX;
+    y = pos[index][1] + netY;
+    z = pos[index][2] + netZ;
+
+    return [x, y, z];
+  }
+};
+
+function emulateNBody(mode, numBodies, ticks) {
+  NBody.init(mode, numBodies);
+  for (var i = 0; i < ticks; i++) {
+    var start = Date.now();
+    if (mode === "par")
+      NBody.tickPar();
+    else
+      NBody.tickSeq();
+    //print(NBody.private.pos);
+    print(mode + " bodies=" + numBodies + " tick=" + (i+1) + "/" + ticks + ": " + (Date.now() - start) + " ms");
+  }
+}
+
+// Using 4000 bodies going off Rick's comment as 4000 being a typical workload.
+const NUMBODIES = 4000;
+const TICKS = 10;
+
+Math.seedrandom("seed");
+
+benchmark("NBODY", 1, DEFAULT_MEASURE,
+          function () { emulateNBody("seq", NUMBODIES, TICKS); },
+          function () { emulateNBody("par", NUMBODIES, TICKS); });
new file mode 100644
--- /dev/null
+++ b/js/src/parjs-benchmarks/seedrandom.js
@@ -0,0 +1,299 @@
+// seedrandom.js version 2.1.
+// Author: David Bau
+// Date: 2013 Mar 16
+//
+// Defines a method Math.seedrandom() that, when called, substitutes
+// an explicitly seeded RC4-based algorithm for Math.random().  Also
+// supports automatic seeding from local or network sources of entropy.
+//
+// http://davidbau.com/encode/seedrandom.js
+// http://davidbau.com/encode/seedrandom-min.js
+//
+// Usage:
+//
+//   <script src=http://davidbau.com/encode/seedrandom-min.js></script>
+//
+//   Math.seedrandom('yay.');  Sets Math.random to a function that is
+//                             initialized using the given explicit seed.
+//
+//   Math.seedrandom();        Sets Math.random to a function that is
+//                             seeded using the current time, dom state,
+//                             and other accumulated local entropy.
+//                             The generated seed string is returned.
+//
+//   Math.seedrandom('yowza.', true);
+//                             Seeds using the given explicit seed mixed
+//                             together with accumulated entropy.
+//
+//   <script src="https://jsonlib.appspot.com/urandom?callback=Math.seedrandom">
+//   </script>                 Seeds using urandom bits from a server.
+//
+// More advanced examples:
+//
+//   Math.seedrandom("hello.");           // Use "hello." as the seed.
+//   document.write(Math.random());       // Always 0.9282578795792454
+//   document.write(Math.random());       // Always 0.3752569768646784
+//   var rng1 = Math.random;              // Remember the current prng.
+//
+//   var autoseed = Math.seedrandom();    // New prng with an automatic seed.
+//   document.write(Math.random());       // Pretty much unpredictable x.
+//
+//   Math.random = rng1;                  // Continue "hello." prng sequence.
+//   document.write(Math.random());       // Always 0.7316977468919549
+//
+//   Math.seedrandom(autoseed);           // Restart at the previous seed.
+//   document.write(Math.random());       // Repeat the 'unpredictable' x.
+//
+//   function reseed(event, count) {      // Define a custom entropy collector.
+//     var t = [];
+//     function w(e) {
+//       t.push([e.pageX, e.pageY, +new Date]);
+//       if (t.length < count) { return; }
+//       document.removeEventListener(event, w);
+//       Math.seedrandom(t, true);        // Mix in any previous entropy.
+//     }
+//     document.addEventListener(event, w);
+//   }
+//   reseed('mousemove', 100);            // Reseed after 100 mouse moves.
+//
+// Version notes:
+//
+// The random number sequence is the same as version 1.0 for string seeds.
+// Version 2.0 changed the sequence for non-string seeds.
+// Version 2.1 speeds seeding and uses window.crypto to autoseed if present.
+//
+// The standard ARC4 key scheduler cycles short keys, which means that
+// seedrandom('ab') is equivalent to seedrandom('abab') and 'ababab'.
+// Therefore it is a good idea to add a terminator to avoid trivial
+// equivalences on short string seeds, e.g., Math.seedrandom(str + '\0').
+// Starting with version 2.0, a terminator is added automatically for
+// non-string seeds, so seeding with the number 111 is the same as seeding
+// with '111\0'.
+//
+// When seedrandom() is called with zero args, it uses a seed
+// drawn from the browser crypto object if present.  If there is no
+// crypto support, seedrandom() uses the current time, the native rng,
+// and a walk of several DOM objects to collect a few bits of entropy.
+//
+// Each time the one- or two-argument forms of seedrandom are called,
+// entropy from the passed seed is accumulated in a pool to help generate
+// future seeds for the zero- and two-argument forms of seedrandom.
+//
+// On speed - This javascript implementation of Math.random() is about
+// 3-10x slower than the built-in Math.random() because it is not native
+// code, but that is typically fast enough.  Some details (timings on
+// Chrome 25 on a 2010 vintage macbook):
+//
+// seeded Math.random()          - avg less than 0.0002 milliseconds per call
+// seedrandom('explicit.')       - avg less than 0.2 milliseconds per call
+// seedrandom('explicit.', true) - avg less than 0.2 milliseconds per call
+// seedrandom() with crypto      - avg less than 0.2 milliseconds per call
+// seedrandom() without crypto   - avg about 12 milliseconds per call
+//
+// On a 2012 windows 7 1.5ghz i5 laptop, Chrome, Firefox 19, IE 10, and
+// Opera have similarly fast timings.  Slowest numbers are on Opera, with
+// about 0.0005 milliseconds per seeded Math.random() and 15 milliseconds
+// for autoseeding.
+//
+// LICENSE (BSD):
+//
+// Copyright 2013 David Bau, 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. Neither the name of this module nor the names of its contributors may
+//      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.
+//
+/**
+ * All code is in an anonymous closure to keep the global namespace clean.
+ */
+(function (
+    global, pool, math, width, chunks, digits) {
+
+//
+// The following constants are related to IEEE 754 limits.
+//
+var startdenom = math.pow(width, chunks),
+    significance = math.pow(2, digits),
+    overflow = significance * 2,
+    mask = width - 1;
+
+//
+// seedrandom()
+// This is the seedrandom function described above.
+//
+math['seedrandom'] = function(seed, use_entropy) {
+  var key = [];
+
+  // Flatten the seed string or build one from local entropy if needed.
+  var shortseed = mixkey(flatten(
+    use_entropy ? [seed, tostring(pool)] :
+    0 in arguments ? seed : autoseed(), 3), key);
+
+  // Use the seed to initialize an ARC4 generator.
+  var arc4 = new ARC4(key);
+
+  // Mix the randomness into accumulated entropy.
+  mixkey(tostring(arc4.S), pool);
+
+  // Override Math.random
+
+  // This function returns a random double in [0, 1) that contains
+  // randomness in every bit of the mantissa of the IEEE 754 value.
+
+  math['random'] = function() {         // Closure to return a random double:
+    var n = arc4.g(chunks),             // Start with a numerator n < 2 ^ 48
+        d = startdenom,                 //   and denominator d = 2 ^ 48.
+        x = 0;                          //   and no 'extra last byte'.
+    while (n < significance) {          // Fill up all significant digits by
+      n = (n + x) * width;              //   shifting numerator and
+      d *= width;                       //   denominator and generating a
+      x = arc4.g(1);                    //   new least-significant-byte.
+    }
+    while (n >= overflow) {             // To avoid rounding up, before adding
+      n /= 2;                           //   last byte, shift everything
+      d /= 2;                           //   right using integer math until
+      x >>>= 1;                         //   we have exactly the desired bits.
+    }
+    return (n + x) / d;                 // Form the number within [0, 1).
+  };
+
+  // Return the seed that was used
+  return shortseed;
+};
+
+//
+// ARC4
+//
+// An ARC4 implementation.  The constructor takes a key in the form of
+// an array of at most (width) integers that should be 0 <= x < (width).
+//
+// The g(count) method returns a pseudorandom integer that concatenates
+// the next (count) outputs from ARC4.  Its return value is a number x
+// that is in the range 0 <= x < (width ^ count).
+//
+/** @constructor */
+function ARC4(key) {
+  var t, keylen = key.length,
+      me = this, i = 0, j = me.i = me.j = 0, s = me.S = [];
+
+  // The empty key [] is treated as [0].
+  if (!keylen) { key = [keylen++]; }
+
+  // Set up S using the standard key scheduling algorithm.
+  while (i < width) {
+    s[i] = i++;
+  }
+  for (i = 0; i < width; i++) {
+    s[i] = s[j = mask & (j + key[i % keylen] + (t = s[i]))];
+    s[j] = t;
+  }
+
+  // The "g" method returns the next (count) outputs as one number.
+  (me.g = function(count) {
+    // Using instance members instead of closure state nearly doubles speed.
+    var t, r = 0,
+        i = me.i, j = me.j, s = me.S;
+    while (count--) {
+      t = s[i = mask & (i + 1)];
+      r = r * width + s[mask & ((s[i] = s[j = mask & (j + t)]) + (s[j] = t))];
+    }
+    me.i = i; me.j = j;
+    return r;
+    // For robust unpredictability discard an initial batch of values.
+    // See http://www.rsa.com/rsalabs/node.asp?id=2009
+  })(width);
+}
+
+//
+// flatten()
+// Converts an object tree to nested arrays of strings.
+//
+function flatten(obj, depth) {
+  var result = [], typ = (typeof obj)[0], prop;
+  if (depth && typ == 'o') {
+    for (prop in obj) {
+      if (obj.hasOwnProperty(prop)) {
+        try { result.push(flatten(obj[prop], depth - 1)); } catch (e) {}
+      }
+    }
+  }
+  return (result.length ? result : typ == 's' ? obj : obj + '\0');
+}
+
+//
+// mixkey()
+// Mixes a string seed into a key that is an array of integers, and
+// returns a shortened string seed that is equivalent to the result key.
+//
+function mixkey(seed, key) {
+  var stringseed = seed + '', smear, j = 0;
+  while (j < stringseed.length) {
+    key[mask & j] =
+      mask & ((smear ^= key[mask & j] * 19) + stringseed.charCodeAt(j++));
+  }
+  return tostring(key);
+}
+
+//
+// autoseed()
+// Returns an object for autoseeding, using window.crypto if available.
+//
+/** @param {Uint8Array=} seed */
+function autoseed(seed) {
+  try {
+    global.crypto.getRandomValues(seed = new Uint8Array(width));
+    return tostring(seed);
+  } catch (e) {
+    return [+new Date, global.document, global.history,
+            global.navigator, global.screen, tostring(pool)];
+  }
+}
+
+//
+// tostring()
+// Converts an array of charcodes to a string
+//
+function tostring(a) {
+  return String.fromCharCode.apply(0, a);
+}
+
+//
+// When seedrandom.js is loaded, we immediately mix a few bits
+// from the built-in RNG into the entropy pool.  Because we do
+// not want to intefere with determinstic PRNG state later,
+// seedrandom will not call math.random on its own again after
+// initialization.
+//
+mixkey(math.random(), pool);
+
+// End anonymous scope, and pass initial values.
+})(
+  this,   // global window object
+  [],     // pool: entropy pool starts empty
+  Math,   // math: package containing random, pow, and seedrandom
+  256,    // width: each RC4 output is 0 <= x < 256
+  6,      // chunks: at least six RC4 outputs for each double
+  52      // digits: there are 52 significant digits in a double
+);