Merge pull request #1891 from opal/elia/random-with-mersenne-twister

random with mersenne twister
opal · Oct 30, 2018 · 371c195 · 371c195
2 parents edc7238 + 3190eed
commit 371c195
Show file tree

Hide file tree

Showing 8 changed files with 187 additions and 11 deletions.
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -70,6 +70,7 @@ Whitespace conventions:
 - Added a new `Opal::Config.missing_require_severity` option and relative `--missing-require` CLI flag. This option will command how the builder will behave when a required file is missing. Previously the behavior was undefined and partly controlled by `dynamic_require_severity`. Not to be confused with the runtime config option `Opal.config.missing_require_severity;` which controls the runtime behavior.
 - Added `Matrix` (along with the internal MRI utility `E2MM`)
 - Use shorter helpers for constant lookups, `$$` for relative (nesting) lookups and `$$$` for absolute (qualified) lookups
+- Add support for the Mersenne Twister random generator, the same used by CRuby/MRI (#657 & #1891)
 
 
 ### Changed

diff --git a/opal/corelib/random.rb b/opal/corelib/random.rb
@@ -1,5 +1,3 @@
-require 'corelib/random/seedrandom.js'
-
 class Random
   attr_reader :seed, :state
 
@@ -11,13 +9,11 @@ def initialize(seed = Random.new_seed)
 
   def reseed(seed)
     @seed = seed
-    `self.$rng = new Math.seedrandom(seed)`
+    `self.$rng = Opal.$$rand.reseed(seed)`
   end
 
-  `var $seed_generator = new Math.seedrandom('opal', { entropy: true })`
-
   def self.new_seed
-    `Math.abs($seed_generator.int32())`
+    `Opal.$$rand.new_seed()`
   end
 
   def self.rand(limit = undefined)
@@ -42,8 +38,6 @@ def self.urandom(size)
     Array.new(size) { rand(255).chr }.join.encode('ASCII-8BIT')
   end
 
-  DEFAULT = new(new_seed)
-
   def ==(other)
     return false unless Random === other
 
@@ -60,7 +54,7 @@ def rand(limit = undefined)
     %x{
       function randomFloat() {
         self.state++;
-        return self.$rng.quick();
+        return Opal.$$rand.rand(self.$rng);
       }
 
       function randomInt() {
@@ -118,4 +112,14 @@ def rand(limit = undefined)
       }
     }
   end
+
+  def self.generator=(generator)
+    `Opal.$$rand = #{generator}`
+
+    if const_defined? :DEFAULT
+      DEFAULT.reseed
+    else
+      const_set :DEFAULT, new(new_seed)
+    end
+  end
 end
diff --git a/opal/corelib/random/MersenneTwister.js b/opal/corelib/random/MersenneTwister.js
@@ -0,0 +1,137 @@
+/*
+This is based on an adaptation of Makoto Matsumoto and Takuji Nishimura's code
+done by Sean McCullough <banksean@gmail.com> and Dave Heitzman
+<daveheitzman@yahoo.com>, subsequently readapted from an updated version of
+ruby's random.c (rev c38a183032a7826df1adabd8aa0725c713d53e1c).
+
+The original copyright notice from random.c follows.
+
+  This is based on trimmed version of MT19937.  To get the original version,
+  contact <http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html>.
+
+  The original copyright notice follows.
+
+     A C-program for MT19937, with initialization improved 2002/2/10.
+     Coded by Takuji Nishimura and Makoto Matsumoto.
+     This is a faster version by taking Shawn Cokus's optimization,
+     Matthe Bellew's simplification, Isaku Wada's real version.
+
+     Before using, initialize the state by using init_genrand(mt, seed)
+     or init_by_array(mt, 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.keio.ac.jp/matumoto/emt.html
+     email: matumoto@math.keio.ac.jp
+*/
+var MersenneTwister = (function() {
+  /* Period parameters */
+  var N = 624;
+  var M = 397;
+  var MATRIX_A = 0x9908b0df;      /* constant vector a */
+  var UMASK = 0x80000000;         /* most significant w-r bits */
+  var LMASK = 0x7fffffff;         /* least significant r bits */
+  var MIXBITS = function(u,v) { return ( ((u) & UMASK) | ((v) & LMASK) ); };
+  var TWIST = function(u,v) { return (MIXBITS((u),(v)) >>> 1) ^ ((v & 0x1) ? MATRIX_A : 0x0); };
+
+  function init(s) {
+    var mt = {left: 0, next: N, state: new Array(N)};
+    init_genrand(mt, s);
+    return mt;
+  }
+
+  /* initializes mt[N] with a seed */
+  function init_genrand(mt, s) {
+    var j, i;
+    mt.state[0] = s >>> 0;
+    for (j=1; j<N; j++) {
+      mt.state[j] = (1812433253 * ((mt.state[j-1] ^ (mt.state[j-1] >> 30) >>> 0)) + j);
+      /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
+      /* In the previous versions, MSBs of the seed affect   */
+      /* only MSBs of the array state[].                     */
+      /* 2002/01/09 modified by Makoto Matsumoto             */
+      mt.state[j] &= 0xffffffff;  /* for >32 bit machines */
+    }
+    mt.left = 1;
+    mt.next = N;
+  }
+
+  /* generate N words at one time */
+  function next_state(mt) {
+    var p = 0, _p = mt.state;
+    var j;
+
+    mt.left = N;
+    mt.next = 0;
+
+    for (j=N-M+1; --j; p++)
+      _p[p] = _p[p+(M)] ^ TWIST(_p[p+(0)], _p[p+(1)]);
+
+    for (j=M; --j; p++)
+      _p[p] = _p[p+(M-N)] ^ TWIST(_p[p+(0)], _p[p+(1)]);
+
+    _p[p] = _p[p+(M-N)] ^ TWIST(_p[p+(0)], _p[0]);
+  }
+
+  /* generates a random number on [0,0xffffffff]-interval */
+  function genrand_int32(mt) {
+    /* mt must be initialized */
+    var y;
+
+    if (--mt.left <= 0) next_state(mt);
+    y = mt.state[mt.next++];
+
+    /* Tempering */
+    y ^= (y >>> 11);
+    y ^= (y << 7) & 0x9d2c5680;
+    y ^= (y << 15) & 0xefc60000;
+    y ^= (y >>> 18);
+
+    return y >>> 0;
+  }
+
+  function int_pair_to_real_exclusive(a, b) {
+    a >>>= 5;
+    b >>>= 6;
+    return(a*67108864.0+b)*(1.0/9007199254740992.0);
+  }
+
+  // generates a random number on [0,1) with 53-bit resolution
+  function genrand_real(mt) {
+    /* mt must be initialized */
+    var a = genrand_int32(mt), b = genrand_int32(mt);
+    return int_pair_to_real_exclusive(a, b);
+  }
+
+  return { genrand_real: genrand_real, init: init };
+})();
diff --git a/opal/corelib/random/math_random.js.rb b/opal/corelib/random/math_random.js.rb
@@ -0,0 +1,9 @@
+class Random
+  MATH_RANDOM_GENERATOR = `{
+    new_seed: function() { return 0; },
+    reseed: function(seed) { return {}; },
+    rand: function($rng) { return Math.random(); }
+  }`
+
+  self.generator = MATH_RANDOM_GENERATOR
+end
diff --git a/opal/corelib/random/mersenne_twister.js.rb b/opal/corelib/random/mersenne_twister.js.rb
@@ -0,0 +1,13 @@
+require 'corelib/random/MersenneTwister'
+
+class Random
+  `var MAX_INT = Number.MAX_SAFE_INTEGER || Math.pow(2, 53) - 1`
+
+  MERSENNE_TWISTER_GENERATOR = `{
+    new_seed: function() { return Math.round(Math.random() * MAX_INT); },
+    reseed: function(seed) { return MersenneTwister.init(seed); },
+    rand: function(mt) { return MersenneTwister.genrand_real(mt); }
+  }`
+
+  self.generator = MERSENNE_TWISTER_GENERATOR
+end
diff --git a/opal/corelib/random/seedrandom.js.rb b/opal/corelib/random/seedrandom.js.rb
@@ -1,5 +1,7 @@
 class Random
   %x{
+    var module = { exports: {} };
+
     /* jshint ignore:start */
     /*
     seedrandom.min.js 2.4.1 (original source: https://github.com/davidbau/seedrandom/blob/2.4.1/seedrandom.min.js)
@@ -11,5 +13,15 @@ class Random
     */
     !function(a,b){function c(c,j,k){var n=[];j=1==j?{entropy:!0}:j||{};var s=g(f(j.entropy?[c,i(a)]:null==c?h():c,3),n),t=new d(n),u=function(){for(var a=t.g(m),b=p,c=0;a<q;)a=(a+c)*l,b*=l,c=t.g(1);for(;a>=r;)a/=2,b/=2,c>>>=1;return(a+c)/b};return u.int32=function(){return 0|t.g(4)},u.quick=function(){return t.g(4)/4294967296},u.double=u,g(i(t.S),a),(j.pass||k||function(a,c,d,f){return f&&(f.S&&e(f,t),a.state=function(){return e(t,{})}),d?(b[o]=a,c):a})(u,s,"global"in j?j.global:this==b,j.state)}function d(a){var b,c=a.length,d=this,e=0,f=d.i=d.j=0,g=d.S=[];for(c||(a=[c++]);e<l;)g[e]=e++;for(e=0;e<l;e++)g[e]=g[f=s&f+a[e%c]+(b=g[e])],g[f]=b;(d.g=function(a){for(var b,c=0,e=d.i,f=d.j,g=d.S;a--;)b=g[e=s&e+1],c=c*l+g[s&(g[e]=g[f=s&f+b])+(g[f]=b)];return d.i=e,d.j=f,c})(l)}function e(a,b){return b.i=a.i,b.j=a.j,b.S=a.S.slice(),b}function f(a,b){var c,d=[],e=typeof a;if(b&&"object"==e)for(c in a)if(a.hasOwnProperty(c))try{d.push(f(a[c],b-1))}catch(a){}return d.length?d:"string"==e?a:a+"\0"}function g(a,b){for(var c,d=a+"",e=0;e<d.length;)b[s&e]=s&(c^=19*b[s&e])+d.charCodeAt(e++);return i(b)}function h(){try{if(j)return i(j.randomBytes(l));var b=new Uint8Array(l);return(k.crypto||k.msCrypto).getRandomValues(b),i(b)}catch(b){var c=k.navigator,d=c&&c.plugins;return[+new Date,k,d,k.screen,i(a)]}}function i(a){return String.fromCharCode.apply(0,a)}var j,k=this,l=256,m=6,n=52,o="random",p=b.pow(l,m),q=b.pow(2,n),r=2*q,s=l-1;if(b["seed"+o]=c,g(b.random(),a),"object"==typeof module&&module.exports){module.exports=c;try{j=require("crypto")}catch(a){}}else"function"==typeof define&&define.amd&&define('seekrandom',function(){return c})}([],Math);
     /* jshint ignore:end */
+    var seedrandom = module.exports
+    var $seed_generator = new Math.seedrandom('opal', { entropy: true })
   }
+
+  SEEDRANDOM_GENERATOR = `{
+    new_seed: function() { return Math.abs($seed_generator.int32()); },
+    reseed: function(seed) { return new seedrandom(seed); },
+    rand: function($rng) { return $rng.quick(); }
+  }`
+
+  self.generator = SEEDRANDOM_GENERATOR
 end
diff --git a/opal/opal.rb b/opal/opal.rb
@@ -13,5 +13,6 @@
 require 'corelib/file'
 require 'corelib/process'
 require 'corelib/random'
+require 'corelib/random/mersenne_twister.js'
 
 require 'corelib/unsupported'
diff --git a/spec/opal/core/iterable_props_spec.rb b/spec/opal/core/iterable_props_spec.rb
@@ -48,7 +48,6 @@
   end
 
   it 'is empty for Math' do
-    # TODO: remove seedrandom.js and fix the test
-    `iterableKeysOf(Math)`.should == ['seedrandom']
+    `iterableKeysOf(Math)`.should == []
   end
 end