time-to-botec

Benchmark sampling in different programming languages
Log | Files | Refs | README

discrete_uniform.js (4031B)

      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 * ## Notice
     20 *
     21 * The original C++ code and copyright notice are from the [Boost library]{http://www.boost.org/doc/libs/1_65_1/doc/html/boost/random/uniform_int_distribution.html}. The implementation has been modified for JavaScript.
     22 *
     23 * ```text
     24 * (C) Copyright John Maddock 2006.
     25 * (C) Copyright Steven Watanabe 2011.
     26 *
     27 * Use, modification and distribution are subject to the
     28 * Boost Software License, Version 1.0. (See accompanying file
     29 * LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt)
     30 * ```
     31 */
     32 
     33 'use strict';
     34 
     35 // MODULES //
     36 
     37 var MAX_SAFE_INTEGER = require( '@stdlib/constants/float64/max-safe-integer' );
     38 var floor = require( '@stdlib/math/base/special/floor' );
     39 
     40 
     41 // MAIN //
     42 
     43 /**
     44 * Returns a pseudorandom number drawn from a discrete uniform distribution with minimum support `a` and maximum support `b`.
     45 *
     46 * @private
     47 * @param {PRNG} rand - pseudorandom number generator which outputs integer values
     48 * @param {integer} a - minimum support
     49 * @param {integer} b - maximum support
     50 * @returns {integer} pseudorandom number
     51 */
     52 function discreteUniform( rand, a, b ) {
     53 	var result;
     54 	var RANGE;
     55 	var range;
     56 	var limit;
     57 	var bsize;
     58 	var mult;
     59 	var MIN;
     60 	var MAX;
     61 	var inc;
     62 
     63 	range = b - a;
     64 	if ( range === 0 ) {
     65 		return a;
     66 	}
     67 	MIN = rand.MIN;
     68 	MAX = rand.MAX;
     69 	RANGE = MAX - MIN;
     70 	if ( RANGE === range ) {
     71 		return ( rand()-MIN ) + a;
     72 	}
     73 	if ( RANGE < range ) {
     74 		limit = 0;
     75 		while ( true ) {
     76 			// Avoid overflow...
     77 			if ( range === MAX_SAFE_INTEGER ) { // in JavaScript, we only explicitly have doubles
     78 				limit = floor( range / (RANGE+1) );
     79 				if ( range%(RANGE+1) === RANGE ) { // e.g., 5%(2+1) == 2
     80 					limit += 1;
     81 				}
     82 			} else {
     83 				limit = floor( (range+1) / (RANGE+1) );
     84 			}
     85 			// We consider `result` as expressed base `(RANGE+1)`:
     86 			result = 0;
     87 
     88 			// For every power of `(RANGE+1)`, we determine a random factor:
     89 			mult = 1;
     90 
     91 			// Loop invariants: result < mult && mult <= range
     92 			while ( mult <= limit ) {
     93 				// Note: see first and second post-conditions.
     94 				result += (rand() - MIN) * mult;
     95 
     96 				// Equivalent to (mult * (RANGE+1)) == range+1, but avoids overflow...
     97 				if ( mult*RANGE === range-mult+1 ) {
     98 					// The destination range is an integer power of the generator's range...
     99 					return result;
    100 				}
    101 				// Note: see third post-condition.
    102 				mult *= RANGE + 1;
    103 			}
    104 			// range/mult < RANGE+1 (no endless loop)
    105 			inc = discreteUniform( rand, 0, floor( range/mult ) );
    106 			if ( inc > MAX_SAFE_INTEGER/mult ) {
    107 				// The multiplication would overflow, so reject immediately...
    108 				continue;
    109 			}
    110 			inc *= mult;
    111 			result += inc;
    112 
    113 			// NOTE: if we were working with unsigned integers, we would need to check that `result` is NOT less than `inc`, as unsigned integers wrap on overflow. In which case, we would need to reject.
    114 
    115 			if ( result > range ) {
    116 				// Result is too big, so reject...
    117 				continue;
    118 			}
    119 			return result + a;
    120 		}
    121 	}
    122 	// Case: RANGE > range
    123 
    124 	// When determining the bucket size, avoid overflow...
    125 	if ( RANGE === MAX_SAFE_INTEGER ) { // in JavaScript, we only explicitly have doubles
    126 		bsize = floor( RANGE / (range+1) );
    127 		if ( RANGE%(range+1) === range ) { // e.g., 5%(2+1) == 2
    128 			bsize += 1;
    129 		}
    130 	} else {
    131 		bsize = floor( (RANGE+1) / (range+1) );
    132 	}
    133 	while ( true ) {
    134 		result = rand() - MIN;
    135 		result = floor( result / bsize );
    136 		if ( result <= range ) {
    137 			return result + a;
    138 		}
    139 	}
    140 }
    141 
    142 
    143 // EXPORTS //
    144 
    145 module.exports = discreteUniform;