javascripts/lecuyer.js

   1 /*
   2
   3     L'Ecuyer's two-sequence generator with a Bays-Durham shuffle
   4     on the back-end.  Schrage's algorithm is used to perform
   5     64-bit modular arithmetic within the 32-bit constraints of
   6     JavaScript.
   7
   8     Bays, C. and S. D. Durham.  ACM Trans. Math. Software: 2 (1976)
   9         59-64.
  10
  11     L'Ecuyer, P.  Communications of the ACM: 31 (1968) 742-774.
  12
  13     Schrage, L.  ACM Trans. Math. Software: 5 (1979) 132-138.
  14
  15 */
  16
  17 function uGen(old, a, q, r, m) {      // Schrage's modular multiplication algorithm
  18     var t;
  19
  20     t = Math.floor(old / q);
  21     t = a * (old - (t * q)) - (t * r);
  22     return Math.round((t < 0) ? (t + m) : t);
  23 }
  24
  25 function LEnext() {                   // Return next raw value
  26     var i;
  27
  28     this.gen1 = uGen(this.gen1, 40014, 53668, 12211, 2147483563);
  29     this.gen2 = uGen(this.gen2, 40692, 52774, 3791, 2147483399);
  30
  31     /* Extract shuffle table index from most significant part
  32        of the previous result. */
  33
  34     i = Math.floor(this.state / 67108862);
  35
  36     // New state is sum of generators modulo one of their moduli
  37
  38     this.state = Math.round((this.shuffle[i] + this.gen2) % 2147483563);
  39
  40     // Replace value in shuffle table with generator 1 result
  41
  42     this.shuffle[i] = this.gen1;
  43
  44     return this.state;
  45 }
  46
  47 //  Return next random integer between 0 and n inclusive
  48
  49 function LEnint(n) {
  50     var p = 1;
  51
  52     //  Determine smallest p,  2^p > n
  53
  54     while (n >= p) {
  55         p <<= 1;
  56     }
  57     p--;
  58
  59     /*  Generate values from 0 through n by first masking
  60         values v from 0 to (2^p)-1, then discarding any results v > n.
  61         For the rationale behind this (and why taking
  62         values mod (n + 1) is biased toward smaller values, see
  63         Ferguson and Schneier, "Practical Cryptography",
  64         ISBN 0-471-22357-3, section 10.8).  */
  65
  66     while (true) {
  67         var v = this.next() & p;
  68
  69         if (v <= n) {
  70             return v;
  71         }
  72     }
  73 }
  74
  75 //  Constructor.  Called with seed value
  76
  77 function LEcuyer(s) {
  78     var i;
  79
  80     this.shuffle = new Array(32);
  81     this.gen1 = this.gen2 = (s & 0x7FFFFFFF);
  82     for (i = 0; i < 19; i++) {
  83         this.gen1 = uGen(this.gen1, 40014, 53668, 12211, 2147483563);
  84     }
  85
  86     // Fill the shuffle table with values
  87
  88     for (i = 0; i < 32; i++) {
  89         this.gen1 = uGen(this.gen1, 40014, 53668, 12211, 2147483563);
  90         this.shuffle[31 - i] = this.gen1;
  91     }
  92     this.state = this.shuffle[0];
  93     this.next = LEnext;
  94     this.nextInt = LEnint;
  95 }