xorshift - npm Package Compare versions

Comparing version 0.1.0 to 0.2.0

LICENSE.md

@@ -1,2 +0,2 @@
-Copyright (c) 2012 Andreas Madsen
+Copyright (c) 2014 Andreas Madsen & Emil Bay
 
@@ -19,2 +19,2 @@ Permission is hereby granted, free of charge, to any person obtaining a copy
 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
-THE SOFTWARE.
+THE SOFTWARE.

package.json

 {
   "name": "xorshift",
-  "description": "Random number generator using xorshift",
-  "version": "0.1.0",
+  "description": "Random number generator using xorshift128+",
+  "version": "0.2.0",
   "author": "Andreas Madsen <[e-mail]>",
+  "contributors": [
+    "Emil Bay <[e-mail]>"
+  ],
   "main": "./xorshift.js",
   "scripts": {
-    "test": "tap test.js"
+    "test": "tap test.js",
+    "benchmark": "node ./benchmark.js"
   },
@@ -10,0 +14,0 @@ "repository" : {

README.md

@@ -1,4 +0,4 @@
-#xorshift
+#xorshift [![Build Status](https://travis-ci.org/AndreasMadsen/xorshift.svg?branch=master)](https://travis-ci.org/AndreasMadsen/xorshift)
 
-> Random number generator using xorshift
+> Random number generator using xorshift128+
 
@@ -8,32 +8,104 @@ ## Installation
 ```sheel
-NOT YET PUBLISHED # npm install xorshift
+# npm install xorshift
 ```
 
-## Documentation
+## Example
 
 ```javascript
-var xorshift = require('xorshift')
-var bview = require('binary-view');
+var xorshift = require('xorshift');
 
 for (var i = 0; i < 10; i++) {
-  console.log(bview(xorshift()));
+  console.log(xorshift.random()); // number in range [0, 1)
 }
 ```
 
-## Testing
+## Documentation
 
-This repo also contains an reference implementation of the 128bit xorshift.
-First you should compile the code.
+This module exports a default pseudo random generator. This generators seed have
+already been set (using `Date.now()`). If this is not suitable a custom
+generator can be initialized using the constructor function
+`xorshift.constructor`. In both cases random numbers can be generated using
+the two methods, `.random` and `.randomint`.
 
-```shell
-gcc -O2 reference.c -o reference
+```javascript
+var xorshift = require('xorshift');
 ```
 
-Next you should execute the binary
+### xorshift.random()
+
+This method returns a random 64bit double, with its value in the range [0, 1).
+That means 0 is inclusive and 1 is exclusive. This is completely similar to
+`Math.random()`.
+
+```javascript
+console.log(xorshift.random()); // number between 0 and 1
+```
+
+This method will serve most purposes, for instance to randomly select between
+2, 3 and 4, this function can be used:
+
+```javascript
+function uniformint(a, b) {
+  return Math.floor(a + xorshift().random() * (b - a));
+}
+
+console.log(uniformint(2, 4));
+```
+
+### xorshift.randomint()
+
+This method returns a random 64bit integer. Since JavaScript don't support
+64bit integers, the number is represented as an array with two elements in
+big-endian order.
+
+This method is useful if high precision is required, the `xorshift.random()`
+method won't allow you to get this precision since a 64bit IEEE754 double
+only contains the 52 most significant bits.
+
+```javascript
+var bview = require('binary-view');
+console.log(bview( new Uint32Array(xorshift.randomint()) ));
+```
+
+### xorshift.constructor
+
+This method is used to construct a new random generator, with a specific seed.
+This can be useful when testing software where random numbers are involved and
+getting consistent results are important.
+
+```javascript
+var XorShift = require('xorshift').constructor;
+var rng1 = new XorShift([1, 0, 2, 0]);
+var rng2 = new XorShift([1, 0, 2, 0]);
+
+assert(rng1.random() === rng2.random());
+```
+
+A `XorShift` instance have both methods `random` and `randomint`. In fact the
+`xorshift` module is an instance of the `XorShift` constructor.
+
+## Reference
+
+This module implements the xorshift128+ pseudo random number generator.
+
+> This is the fastest generator passing BigCrush without systematic
+> errors, but due to the relatively short period it is acceptable only
+> for applications with a very mild amount of parallelism; otherwise, use
+> a xorshift1024* generator.
+> – <cite> http://xorshift.di.unimi.it </cite>
+
+This source also have a
+[reference implementation](http://xorshift.di.unimi.it/xorshift128plus.c)
+for the xorshift128+ generator. A wrapper around this implementation have been
+created and is used for testing this module. To compile and run it:
+
 ```shell
-./reference <numbers>
+gcc -O2 reference.c -o reference
+./reference <numbers> <seed0> <seed1>
 ```
 
-`<numbers>` can be any number greater than zero, and it will be the amount
+* `<numbers>` can be any number greater than zero, and it will be the amount
 if random numbers in the stdout. The default value is `10`.
+* `<seed0>` and `<seed1>` forms the 128bit seed that the algorithm uses. Default
+is `[1, 2]`.
 
@@ -44,3 +116,3 @@ ##License
 
-> Copyright (c) 2014
+> Copyright (c) 2014 Andreas Madsen & Emil Bay
 >
@@ -47,0 +119,0 @@ > Permission is hereby granted, free of charge, to any person obtaining a copy

test.js

 
-var os = require('os');
 var test = require('tap').test;
+var xorshift = require('./xorshift.js');
+
+var reference = require('./reference.json');
+
+function hexview(arr) {
+  var a = arr[0].toString(16);
+  var b = arr[1].toString(16);
+
+  a = (new Array(9 - a.length)).join(0) + a;
+  b = (new Array(9 - b.length)).join(0) + b;
+
+  return (a + b).toUpperCase();
+}
+
+test('random double', function (t) {
+  t.test('with seed = [1, 2]', function (t) {
+    var ref = reference['1-2'];
+    var rng = xorshift.constructor([0, 1, 0, 2]);
+    for (var i = 0; i < ref.length; i++) {
+      t.equal(rng.random(), parseInt(ref[i], 16) / Math.pow(2, 64));
+    }
+
+    t.end();
+  });
+
+  t.test('with seed = [3, 4]', function (t) {
+    var ref = reference['3-4'];
+    var rng = xorshift.constructor([0, 3, 0, 4]);
+    for (var i = 0; i < ref.length; i++) {
+      t.equal(rng.random(), parseInt(ref[i], 16) / Math.pow(2, 64));
+    }
+
+    t.end();
+  });
+
+  t.end();
+});
+
+test('random int array', function (t) {
+  t.test('with seed = [1, 2]', function (t) {
+    var ref = reference['1-2'];
+    var rng = xorshift.constructor([0, 1, 0, 2]);
+    for (var i = 0; i < ref.length; i++) {
+      t.strictEqual(hexview(rng.randomint()), ref[i]);
+    }
+
+    t.end();
+  });
+
+  t.test('with seed = [3, 4]', function (t) {
+    var ref = reference['3-4'];
+    var rng = xorshift.constructor([0, 3, 0, 4]);
+    for (var i = 0; i < ref.length; i++) {
+      t.strictEqual(hexview(rng.randomint()), ref[i]);
+    }
+
+    t.end();
+  });
+
+  t.end();
+});
+
+test('default instance', function (t) {
+  t.test('random int', function (t) {
+    // demand that the 100 first outputs are different
+    var obj = Object.create(null);
+    for (var i = 0; i< 100; i++) {
+      obj[hexview(xorshift.randomint())] = 1;
+    }
+    t.equal(Object.keys(obj).length, 100);
+    t.end();
+  });
+
+  t.test('random double', function (t) {
+    // demand that the 100 first outputs are different
+    var obj = Object.create(null);
+    for (var i = 0; i< 100; i++) {
+      var rand = xorshift.random();
+      obj[rand.toExponential(20)] = 1;
+      t.ok(rand >= 0 && rand < 1, 'random double is [0, 1)');
+    }
+    t.equal(Object.keys(obj).length, 100);
+    t.end();
+  });
+  t.end();
+});
+
+test('bad initialization', function (t) {
+  t.test('wrong input type', function (t) {
+    var error = null;
+    try {
+      xorshift.constructor("0102");
+    } catch (e) { error = e; }
+
+    t.equal(error.name, 'TypeError');
+    t.equal(error.message, 'seed must be an array with 4 numbers');
+    t.end();
+  });
+
+  t.test('wrong array length', function (t) {
+    var error = null;
+    try {
+      xorshift.constructor([1, 2, 0]);
+    } catch (e) { error = e; }
+
+    t.equal(error.name, 'TypeError');
+    t.equal(error.message, 'seed must be an array with 4 numbers');
+    t.end();
+  });
+
+  t.end();
+});

xorshift.js

 
-var bview = require('binary-view');
+/**
+ * Create a pseudorandom number generator, with a seed.
+ * @param {array} seed "128-bit" integer, composed of 4x32-bit
+ * integers in big endian order.
+ */
+function XorShift(seed) {
+  // Note the extension, this === module.exports is required because
+  // the `constructor` function will be used to generate new instances.
+  // In that case `this` will point to the default RNG, and `this` will
+  // be an instance of XorShift.
+  if (!(this instanceof XorShift) || this === module.exports) {
+    return new XorShift(seed);
+  }
 
-var s = new Uint32Array(4);
-var s16 = new Uint16Array(s.buffer);
+  if (!Array.isArray(seed) || seed.length !== 4) {
+    throw new TypeError('seed must be an array with 4 numbers');
+  }
 
-function leftShift(read, write, amount) {
-  var s0 = read[0];
-  var s1 = read[1];
-
-  var m = 0xFFFFFFFF << (32 - amount);
-  write[0] = (s0 << amount) | ((s1 & m) >>> (32 - amount));
-  write[1] = s1 << amount;
+  // uint64_t s = [seed ...]
+  this._state0U = seed[0] | 0;
+  this._state0L = seed[1] | 0;
+  this._state1U = seed[2] | 0;
+  this._state1L = seed[3] | 0;
 }
 
-function xor(readA, readB, write) {
-  write[0] = readA[0] ^ readB[0];
-  write[1] = readA[1] ^ readB[1];
-}
+/**
+ * Returns a 64bit random number as a 2x32bit array
+ * @return {array}
+ */
+XorShift.prototype.randomint = function() {
+  // uint64_t s1 = s[0]
+  var s1U = this._state0U, s1L = this._state0L;
+  // uint64_t s0 = s[1]
+  var s0U = this._state1U, s0L = this._state1L;
 
-function rightShift(read, write, amount) {
-  var s0 = read[0];
-  var s1 = read[1];
+  // s[0] = s0
+  this._state0U = s0U;
+  this._state0L = s0L;
 
-  var m = 0xFFFFFFFF >>> (32 - amount);
-  write[1] = (s1 >>> amount) | ((s0 & m) << (32 - amount));
-  write[0] = s0 >>> amount;
-}
+  // - t1 = [0, 0]
+  var t1U = 0, t1L = 0;
+  // - t2 = [0, 0]
+  var t2U = 0, t2L = 0;
 
-function add(readA, readB, write) {
-  var readA16 = new Uint16Array(readA.buffer);
-  var readB16 = new Uint16Array(readB.buffer);
-  var write16 = new Uint16Array(write.buffer);
+  // s1 ^= s1 << 23;
+  // :: t1 = s1 << 23
+  var a1 = 23;
+  var m1 = 0xFFFFFFFF << (32 - a1);
+  t1U = (s1U << a1) | ((s1L & m1) >>> (32 - a1));
+  t1L = s1L << a1;
+  // :: s1 = s1 ^ t1
+  s1U = s1U ^ t1U;
+  s1L = s1L ^ t1L;
 
-  var a00 = readA16[2];
-  var a01 = readA16[3];
-  var a10 = readA16[0];
-  var a11 = readA16[1];
+  // t1 = ( s1 ^ s0 ^ ( s1 >> 17 ) ^ ( s0 >> 26 ) )
+  // :: t1 = s1 ^ s0
+  t1U = s1U ^ s0U;
+  t1L = s1L ^ s0L;
+  // :: t2 = s1 >> 17
+  var a2 = 17;
+  var m2 = 0xFFFFFFFF >>> (32 - a2);
+  t2U = s1U >>> a2;
+  t2L = (s1L >>> a2) | ((s1U & m2) << (32 - a2));
+  // :: t1 = t1 ^ t2
+  t1U = t1U ^ t2U;
+  t1L = t1L ^ t2L;
+  // :: t2 = s0 >> 26
+  var a3 = 26;
+  var m3 = 0xFFFFFFFF >>> (32 - a3);
+  t2U = s0U >>> a3;
+  t2L = (s0L >>> a3) | ((s0U & m3) << (32 - a3));
+  // :: t1 = t1 ^ t2
+  t1U = t1U ^ t2U;
+  t1L = t1L ^ t2L;
 
-  var b00 = readB16[2];
-  var b01 = readB16[3];
-  var b10 = readB16[0];
-  var b11 = readB16[1];
+  // s[1] = t1
+  this._state1U = t1U;
+  this._state1L = t1L;
 
-  c00 = a00 + b00;
-  c01 = a01 + b01 + (c00 >>> 16);
-  c10 = a10 + b10 + (c01 >>> 16);
-  c11 = a11 + b11 + (c10 >>> 16);
+  // return t1 + s0
+  // :: t2 = t1 + s0
+  var sumL = (t1L >>> 0) + (s0L >>> 0);
+  t2U = (t1U + s0U + (sumL / 2 >>> 31)) >>> 0;
+  t2L = sumL >>> 0;
 
-  write16[2] = c00;
-  write16[3] = c01;
-  write16[0] = c10;
-  write16[1] = c11;
-}
+  // :: ret t2
+  return [t2U, t2L];
+};
 
-s[1] = 1;
-s[3] = 2;
+/**
+ * Returns a random number normalized [0, 1), just like Math.random()
+ * @return {number}
+ */
+XorShift.prototype.random = function() {
+  var t2 = this.randomint();
 
-function xorshift() {
-  var t1 = new Uint32Array(2);
-  var t2 = new Uint32Array(2);
+  // :: ret t2 / 2**64
+  return (t2[0] * 4294967296 + t2[1]) / 18446744073709551616;
+};
 
-  // uint64_t s1 = s[ 0 ];
-  var s1 = new Uint32Array(s.subarray(0, 2));
 
-  // const uint64_t s0 = s[ 1 ];
-  var s0 = new Uint32Array(s.subarray(2, 4));
+// There is nothing particularly scientific about this seed, it is just
+// based on the clock.
+module.exports = new XorShift([
+  0, Date.now() / 65536,
+  0, Date.now() % 65536
+]);
 
-  // s[ 0 ] = s0;
-  s[0] = s0[0];
-  s[1] = s0[1];
-
-  // s1 ^= s1 << 23;
-  leftShift(s1, t1, 23);
-  xor(s1, t1, s1);
-
-  // k = ( s1 ^ s0 ^ ( s1 >> 17 ) ^ ( s0 >> 26 ) )
-  xor(s1, s0, t1);
-  rightShift(s1, t2, 17);
-  xor(t1, t2, t1);
-  rightShift(s0, t2, 26);
-  xor(t1, t2, t1);
-
-  // s[1] = k
-  s[2] = t1[0];
-  s[3] = t1[1];
-
-  // return k + s0
-  add(t1, s0, t2);
-
-  return t2;
-}
-
-module.exports = xorshift;
+// Perform 20 iterations in the RNG, this prevens a short seed from generating
+// pseudo predictable number.
+(function () {
+  var rng = module.exports;
+  for (var i = 0; i < 20; i++) {
+    rng.randomint();
+  }
+})();

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

17943

increased by207.56%

Number of package files

11

increased by57.14%

Lines of code

416

increased by469.86%

Number of lines in readme file

134

increased by116.13%

Worsened metrics

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes