factory.js (17039B)
1 /** 2 * @license Apache-2.0 3 * 4 * Copyright (c) 2018 The Stdlib Authors. 5 * 6 * Licensed under the Apache License, Version 2.0 (the "License"); 7 * you may not use this file except in compliance with the License. 8 * You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, software 13 * distributed under the License is distributed on an "AS IS" BASIS, 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15 * See the License for the specific language governing permissions and 16 * limitations under the License. 17 */ 18 19 /* eslint-disable max-len */ 20 21 'use strict'; 22 23 // MODULES // 24 25 var setReadOnly = require( '@stdlib/utils/define-nonenumerable-read-only-property' ); 26 var setReadOnlyAccessor = require( '@stdlib/utils/define-nonenumerable-read-only-accessor' ); 27 var setReadWriteAccessor = require( '@stdlib/utils/define-nonenumerable-read-write-accessor' ); 28 var hasOwnProp = require( '@stdlib/assert/has-own-property' ); 29 var isObject = require( '@stdlib/assert/is-plain-object' ); 30 var isBoolean = require( '@stdlib/assert/is-boolean' ).isPrimitive; 31 var isCollection = require( '@stdlib/assert/is-collection' ); 32 var isPositiveInteger = require( '@stdlib/assert/is-positive-integer' ).isPrimitive; 33 var isInt32Array = require( '@stdlib/assert/is-int32array' ); 34 var gcopy = require( '@stdlib/blas/base/gcopy' ); 35 var floor = require( '@stdlib/math/base/special/floor' ); 36 var Int32Array = require( '@stdlib/array/int32' ); 37 var INT32_MAX = require( '@stdlib/constants/int32/max' ); 38 var typedarray2json = require( '@stdlib/array/to-json' ); 39 var createTable = require( './create_table.js' ); 40 var randint32 = require( './rand_int32.js' ); 41 42 43 // VARIABLES // 44 45 var NORMALIZATION_CONSTANT = (INT32_MAX - 1)|0; // asm type annotation 46 var MAX_SEED = (INT32_MAX - 1)|0; // asm type annotation 47 var A = 16807|0; // asm type annotation 48 49 // Define the number of elements in the shuffle table: 50 var TABLE_LENGTH = 32; 51 52 // Define the state array schema version: 53 var STATE_ARRAY_VERSION = 1; // NOTE: anytime the state array schema changes, this value should be incremented!!! 54 55 // Define the number of sections in the state array: 56 var NUM_STATE_SECTIONS = 3; // table, other, seed 57 58 // Define the index offset of the "table" section in the state array: 59 var TABLE_SECTION_OFFSET = 2; // | version | num_sections | table_length | ...table | other_length | shuffle_state | prng_state | seed_length | ...seed | 60 61 // Define the index offset of the "state" section in the state array: 62 var STATE_SECTION_OFFSET = TABLE_LENGTH + 3; // | version | num_sections | table_length | ...table | state_length | shuffle_state | prng_state | seed_length | ...seed | 63 64 // Define the index offset of the seed section in the state array: 65 var SEED_SECTION_OFFSET = TABLE_LENGTH + 6; // | version | num_sections | table_length | ...table | state_length | shuffle_state | prng_state | seed_length | ...seed | 66 67 // Define the length of the "fixed" length portion of the state array: 68 var STATE_FIXED_LENGTH = TABLE_LENGTH + 7; // 1 (version) + 1 (num_sections) + 1 (table_length) + TABLE_LENGTH (table) + 1 (state_length) + 1 (shuffle_state) + 1 (prng_state) + 1 (seed_length) 69 70 // Define the indices for the shuffle table and PRNG states: 71 var SHUFFLE_STATE = STATE_SECTION_OFFSET + 1; 72 var PRNG_STATE = STATE_SECTION_OFFSET + 2; 73 74 75 // FUNCTIONS // 76 77 /** 78 * Verifies state array integrity. 79 * 80 * @private 81 * @param {Int32Array} state - state array 82 * @param {boolean} FLG - flag indicating whether the state array was provided as an option (true) or an argument (false) 83 * @returns {(Error|null)} an error or `null` 84 */ 85 function verifyState( state, FLG ) { 86 var s1; 87 if ( FLG ) { 88 s1 = 'option'; 89 } else { 90 s1 = 'argument'; 91 } 92 // The state array must have a minimum length... 93 if ( state.length < STATE_FIXED_LENGTH+1 ) { 94 return new RangeError( 'invalid '+s1+'. `state` array has insufficient length.' ); 95 } 96 // The first element of the state array must equal the supported state array schema version... 97 if ( state[ 0 ] !== STATE_ARRAY_VERSION ) { 98 return new RangeError( 'invalid '+s1+'. `state` array has an incompatible schema version. Expected: '+STATE_ARRAY_VERSION+'. Actual: '+state[ 0 ]+'.' ); 99 } 100 // The second element of the state array must contain the number of sections... 101 if ( state[ 1 ] !== NUM_STATE_SECTIONS ) { 102 return new RangeError( 'invalid '+s1+'. `state` array has an incompatible number of sections. Expected: '+NUM_STATE_SECTIONS+'. Actual: '+state[ 1 ]+'.' ); 103 } 104 // The length of the "table" section must equal `TABLE_LENGTH`... 105 if ( state[ TABLE_SECTION_OFFSET ] !== TABLE_LENGTH ) { 106 return new RangeError( 'invalid '+s1+'. `state` array has an incompatible table length. Expected: '+TABLE_LENGTH+'. Actual: '+state[ TABLE_SECTION_OFFSET ]+'.' ); 107 } 108 // The length of the "state" section must equal `2`... 109 if ( state[ STATE_SECTION_OFFSET ] !== 2 ) { 110 return new RangeError( 'invalid '+s1+'. `state` array has an incompatible state length. Expected: '+(2).toString()+'. Actual: '+state[ STATE_SECTION_OFFSET ]+'.' ); 111 } 112 // The length of the "seed" section much match the empirical length... 113 if ( state[ SEED_SECTION_OFFSET ] !== state.length-STATE_FIXED_LENGTH ) { 114 return new RangeError( 'invalid '+s1+'. `state` array length is incompatible with seed section length. Expected: '+(state.length-STATE_FIXED_LENGTH)+'. Actual: '+state[ SEED_SECTION_OFFSET ]+'.' ); 115 } 116 return null; 117 } 118 119 120 // MAIN // 121 122 /** 123 * Returns a linear congruential pseudorandom number generator (LCG) whose output is shuffled. 124 * 125 * @param {Options} [options] - options 126 * @param {PRNGSeedMINSTD} [options.seed] - pseudorandom number generator seed 127 * @param {PRNGStateMINSTD} [options.state] - pseudorandom number generator state 128 * @param {boolean} [options.copy=true] - boolean indicating whether to copy a provided pseudorandom number generator state 129 * @throws {TypeError} options argument must be an object 130 * @throws {TypeError} a seed must be either a positive integer less than the maximum signed 32-bit integer or an array-like object containing integers less than the maximum signed 32-bit integer 131 * @throws {RangeError} a numeric seed must be a positive integer less than the maximum signed 32-bit integer 132 * @throws {TypeError} state must be an `Int32Array` 133 * @throws {Error} must provide a valid state 134 * @throws {TypeError} `copy` option must be a boolean 135 * @returns {PRNG} shuffled LCG PRNG 136 * 137 * @example 138 * var minstd = factory(); 139 * 140 * var v = minstd(); 141 * // returns <number> 142 * 143 * @example 144 * // Return a seeded LCG: 145 * var minstd = factory({ 146 * 'seed': 1234 147 * }); 148 * 149 * var v = minstd(); 150 * // returns 1421600654 151 */ 152 function factory( options ) { 153 var STATE; 154 var state; 155 var opts; 156 var seed; 157 var slen; 158 var err; 159 160 opts = {}; 161 if ( arguments.length ) { 162 if ( !isObject( options ) ) { 163 throw new TypeError( 'invalid argument. Options argument must be an object. Value: `' + options + '`.' ); 164 } 165 if ( hasOwnProp( options, 'copy' ) ) { 166 opts.copy = options.copy; 167 if ( !isBoolean( options.copy ) ) { 168 throw new TypeError( 'invalid option. `copy` option must be a boolean. Option: `' + options.copy + '`.' ); 169 } 170 } 171 if ( hasOwnProp( options, 'state' ) ) { 172 state = options.state; 173 opts.state = true; 174 if ( !isInt32Array( state ) ) { 175 throw new TypeError( 'invalid option. `state` option must be an Int32Array. Option: `' + state + '`.' ); 176 } 177 err = verifyState( state, true ); 178 if ( err ) { 179 throw err; 180 } 181 if ( opts.copy === false ) { 182 STATE = state; 183 } else { 184 STATE = new Int32Array( state.length ); 185 gcopy( state.length, state, 1, STATE, 1 ); 186 } 187 // Create a state (table) "view": 188 state = new Int32Array( STATE.buffer, STATE.byteOffset+((TABLE_SECTION_OFFSET+1)*STATE.BYTES_PER_ELEMENT), TABLE_LENGTH ); 189 190 // Create a seed "view": 191 seed = new Int32Array( STATE.buffer, STATE.byteOffset+((SEED_SECTION_OFFSET+1)*STATE.BYTES_PER_ELEMENT), state[ SEED_SECTION_OFFSET ] ); 192 } 193 // If provided a PRNG state, we ignore the `seed` option... 194 if ( seed === void 0 ) { 195 if ( hasOwnProp( options, 'seed' ) ) { 196 seed = options.seed; 197 opts.seed = true; 198 if ( isPositiveInteger( seed ) ) { 199 if ( seed > MAX_SEED ) { 200 throw new RangeError( 'invalid option. `seed` option must be a positive integer less than the maximum signed 32-bit integer. Option: `' + seed + '`.' ); 201 } 202 seed |= 0; // asm type annotation 203 } else if ( isCollection( seed ) && seed.length > 0 ) { 204 slen = seed.length; 205 STATE = new Int32Array( STATE_FIXED_LENGTH+slen ); 206 207 // Initialize sections: 208 STATE[ 0 ] = STATE_ARRAY_VERSION; 209 STATE[ 1 ] = NUM_STATE_SECTIONS; 210 STATE[ TABLE_SECTION_OFFSET ] = TABLE_LENGTH; 211 STATE[ STATE_SECTION_OFFSET ] = 2; 212 STATE[ PRNG_STATE ] = seed[ 0 ]; 213 STATE[ SEED_SECTION_OFFSET ] = slen; 214 215 // Copy the provided seed array to prevent external mutation, as mutation would lead to an inability to reproduce PRNG values according to the PRNG's stated seed: 216 gcopy.ndarray( slen, seed, 1, 0, STATE, 1, SEED_SECTION_OFFSET+1 ); 217 218 // Create a state (table) "view": 219 state = new Int32Array( STATE.buffer, STATE.byteOffset+((TABLE_SECTION_OFFSET+1)*STATE.BYTES_PER_ELEMENT), TABLE_LENGTH ); 220 221 // Create a seed "view": 222 seed = new Int32Array( STATE.buffer, STATE.byteOffset+((SEED_SECTION_OFFSET+1)*STATE.BYTES_PER_ELEMENT), slen ); 223 224 // Initialize the internal PRNG state: 225 state = createTable( minstd, state, TABLE_LENGTH ); 226 STATE[ SHUFFLE_STATE ] = state[ 0 ]; 227 } else { 228 throw new TypeError( 'invalid option. `seed` option must be either a positive integer less than the maximum signed 32-bit integer or an array-like object containing integer values less than the maximum signed 32-bit integer. Option: `' + seed + '`.' ); 229 } 230 } else { 231 seed = randint32()|0; // asm type annotation 232 } 233 } 234 } else { 235 seed = randint32()|0; // asm type annotation 236 } 237 if ( state === void 0 ) { 238 STATE = new Int32Array( STATE_FIXED_LENGTH+1 ); 239 240 // Initialize sections: 241 STATE[ 0 ] = STATE_ARRAY_VERSION; 242 STATE[ 1 ] = NUM_STATE_SECTIONS; 243 STATE[ TABLE_SECTION_OFFSET ] = TABLE_LENGTH; 244 STATE[ STATE_SECTION_OFFSET ] = 2; 245 STATE[ PRNG_STATE ] = seed; 246 STATE[ SEED_SECTION_OFFSET ] = 1; 247 STATE[ SEED_SECTION_OFFSET+1 ] = seed; 248 249 // Create a state (table) "view": 250 state = new Int32Array( STATE.buffer, STATE.byteOffset+((TABLE_SECTION_OFFSET+1)*STATE.BYTES_PER_ELEMENT), TABLE_LENGTH ); 251 252 // Create a seed "view": 253 seed = new Int32Array( STATE.buffer, STATE.byteOffset+((SEED_SECTION_OFFSET+1)*STATE.BYTES_PER_ELEMENT), 1 ); 254 255 // Initialize the internal PRNG state: 256 state = createTable( minstd, state, TABLE_LENGTH ); 257 STATE[ SHUFFLE_STATE ] = state[ 0 ]; 258 } 259 setReadOnly( minstdShuffle, 'NAME', 'minstd-shuffle' ); 260 setReadOnlyAccessor( minstdShuffle, 'seed', getSeed ); 261 setReadOnlyAccessor( minstdShuffle, 'seedLength', getSeedLength ); 262 setReadWriteAccessor( minstdShuffle, 'state', getState, setState ); 263 setReadOnlyAccessor( minstdShuffle, 'stateLength', getStateLength ); 264 setReadOnlyAccessor( minstdShuffle, 'byteLength', getStateSize ); 265 setReadOnly( minstdShuffle, 'toJSON', toJSON ); 266 setReadOnly( minstdShuffle, 'MIN', 1 ); 267 setReadOnly( minstdShuffle, 'MAX', INT32_MAX-1 ); 268 setReadOnly( minstdShuffle, 'normalized', normalized ); 269 270 setReadOnly( normalized, 'NAME', minstdShuffle.NAME ); 271 setReadOnlyAccessor( normalized, 'seed', getSeed ); 272 setReadOnlyAccessor( normalized, 'seedLength', getSeedLength ); 273 setReadWriteAccessor( normalized, 'state', getState, setState ); 274 setReadOnlyAccessor( normalized, 'stateLength', getStateLength ); 275 setReadOnlyAccessor( normalized, 'byteLength', getStateSize ); 276 setReadOnly( normalized, 'toJSON', toJSON ); 277 setReadOnly( normalized, 'MIN', (minstdShuffle.MIN-1.0) / NORMALIZATION_CONSTANT ); 278 setReadOnly( normalized, 'MAX', (minstdShuffle.MAX-1.0) / NORMALIZATION_CONSTANT ); 279 280 return minstdShuffle; 281 282 /** 283 * Returns the PRNG seed. 284 * 285 * @private 286 * @returns {PRNGSeedMINSTD} seed 287 */ 288 function getSeed() { 289 var len = STATE[ SEED_SECTION_OFFSET ]; 290 return gcopy( len, seed, 1, new Int32Array( len ), 1 ); 291 } 292 293 /** 294 * Returns the PRNG seed length. 295 * 296 * @private 297 * @returns {PositiveInteger} seed length 298 */ 299 function getSeedLength() { 300 return STATE[ SEED_SECTION_OFFSET ]; 301 } 302 303 /** 304 * Returns the PRNG state length. 305 * 306 * @private 307 * @returns {PositiveInteger} state length 308 */ 309 function getStateLength() { 310 return STATE.length; 311 } 312 313 /** 314 * Returns the PRNG state size (in bytes). 315 * 316 * @private 317 * @returns {PositiveInteger} state size (in bytes) 318 */ 319 function getStateSize() { 320 return STATE.byteLength; 321 } 322 323 /** 324 * Returns the current PRNG state. 325 * 326 * ## Notes 327 * 328 * - The PRNG state array is comprised of a preamble followed by `3` sections: 329 * 330 * 0. preamble (version + number of sections) 331 * 1. shuffle table 332 * 2. internal PRNG state 333 * 3. PRNG seed 334 * 335 * - The first element of the PRNG state array preamble is the state array schema version. 336 * 337 * - The second element of the PRNG state array preamble is the number of state array sections (i.e., `3`). 338 * 339 * - The first element of each section following the preamble specifies the section length. The remaining section elements comprise the section contents. 340 * 341 * @private 342 * @returns {PRNGStateMINSTD} current state 343 */ 344 function getState() { 345 var len = STATE.length; 346 return gcopy( len, STATE, 1, new Int32Array( len ), 1 ); 347 } 348 349 /** 350 * Sets the PRNG state. 351 * 352 * ## Notes 353 * 354 * - If PRNG state is "shared" (meaning a state array was provided during PRNG creation and **not** copied) and one sets the generator state to a state array having a different length, the PRNG does **not** update the existing shared state and, instead, points to the newly provided state array. In order to synchronize PRNG output according to the new shared state array, the state array for **each** relevant PRNG must be **explicitly** set. 355 * - If PRNG state is "shared" and one sets the generator state to a state array of the same length, the PRNG state is updated (along with the state of all other PRNGs sharing the PRNG's state array). 356 * 357 * @private 358 * @param {PRNGStateMINSTD} s - generator state 359 * @throws {TypeError} must provide an `Int32Array` 360 * @throws {Error} must provide a valid state 361 */ 362 function setState( s ) { 363 var err; 364 if ( !isInt32Array( s ) ) { 365 throw new TypeError( 'invalid argument. Must provide an Int32Array. Value: `' + s + '`.' ); 366 } 367 err = verifyState( s, false ); 368 if ( err ) { 369 throw err; 370 } 371 if ( opts.copy === false ) { 372 if ( opts.state && s.length === STATE.length ) { 373 gcopy( s.length, s, 1, STATE, 1 ); // update current shared state 374 } else { 375 STATE = s; // point to new shared state 376 opts.state = true; // setting this flag allows updating a shared state even if a state array was not provided at PRNG creation 377 } 378 } else { 379 // Check if we can reuse allocated memory... 380 if ( s.length !== STATE.length ) { 381 STATE = new Int32Array( s.length ); // reallocate 382 } 383 gcopy( s.length, s, 1, STATE, 1 ); 384 } 385 // Create a new state (table) "view": 386 state = new Int32Array( STATE.buffer, STATE.byteOffset+((TABLE_SECTION_OFFSET+1)*STATE.BYTES_PER_ELEMENT), TABLE_LENGTH ); 387 388 // Create a new seed "view": 389 seed = new Int32Array( STATE.buffer, STATE.byteOffset+((SEED_SECTION_OFFSET+1)*STATE.BYTES_PER_ELEMENT), STATE[ SEED_SECTION_OFFSET ] ); 390 } 391 392 /** 393 * Serializes the pseudorandom number generator as a JSON object. 394 * 395 * ## Notes 396 * 397 * - `JSON.stringify()` implicitly calls this method when stringifying a PRNG. 398 * 399 * @private 400 * @returns {Object} JSON representation 401 */ 402 function toJSON() { 403 var out = {}; 404 out.type = 'PRNG'; 405 out.name = minstdShuffle.NAME; 406 out.state = typedarray2json( STATE ); 407 out.params = []; 408 return out; 409 } 410 411 /** 412 * Generates a pseudorandom integer on the interval \\( [1,2^{31}-1) \\). 413 * 414 * @private 415 * @returns {integer32} pseudorandom integer 416 */ 417 function minstd() { 418 var s = STATE[ PRNG_STATE ]|0; // asm type annotation 419 s = ( (A*s)%INT32_MAX )|0; // asm type annotation 420 STATE[ PRNG_STATE ] = s; 421 return s|0; // asm type annotation 422 } 423 424 /** 425 * Generates a pseudorandom integer on the interval \\( [1,2^{31}-1) \\). 426 * 427 * @private 428 * @returns {integer32} pseudorandom integer 429 * 430 * @example 431 * var v = minstd(); 432 * // returns <number> 433 */ 434 function minstdShuffle() { 435 var s; 436 var i; 437 438 s = STATE[ SHUFFLE_STATE ]; 439 i = floor( TABLE_LENGTH * (s/INT32_MAX) ); 440 441 // Pull a state from the table: 442 s = state[ i ]; 443 444 // Update the PRNG state: 445 STATE[ SHUFFLE_STATE ] = s; 446 447 // Replace the pulled state: 448 state[ i ] = minstd(); 449 450 return s; 451 } 452 453 /** 454 * Generates a pseudorandom number on the interval \\( [0,1) \\). 455 * 456 * @private 457 * @returns {number} pseudorandom number 458 * 459 * @example 460 * var v = normalized(); 461 * // returns <number> 462 */ 463 function normalized() { 464 return (minstdShuffle()-1) / NORMALIZATION_CONSTANT; 465 } 466 } 467 468 469 // EXPORTS // 470 471 module.exports = factory;