I want a randomInt function that can handle the full range of Number.MIN_SAFE_INTEGER to Number.MAX_SAFE_INTEGER and that the values returned are uniformly distributed.
So, I started at MDN and looked at the Math.random page. They give an example, which appears to be uniformly distributed.
// Returns a random integer between min (included) and max (excluded)
// Using Math.round() will give you a non-uniform distribution!
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min)) + min;
}
But it comes with the following note.
Note that as numbers in JavaScript are IEEE 754 floating point numbers with round-to-nearest-even behavior, the ranges claimed for the functions below (excluding the one for Math.random() itself) aren't exact. If extremely large bounds are chosen (2^53 or higher), it's possible in extremely rare cases to calculate the usually-excluded upper bound.
I'm wanting to use the range -(2^53 - 1) and 2^53 - 1, so I believe that this note does not apply. I then notice max - min: this is going to be a problem for the range that I have specified:
Number.MAX_SAFE_INTEGER - Number.MIN_SAFE_INTEGER > Number.MAX_SAFE_INTEGER
Off I go and have a little play and come up with the following code, based on the MDN example and my requirements.
Number.MAX_SAFE_INTEGER = Number.MAX_SAFE_INTEGER || 9007199254740991;
Number.MIN_SAFE_INTEGER = Number.MIN_SAFE_INTEGER || -Number.MAX_SAFE_INTEGER;
Number.toInteger = Number.toInteger || function (inputArg) {
var number = +inputArg,
val = 0;
if (number === number) {
if (!number || number === Infinity || number === -Infinity) {
val = number;
} else {
val = (number > 0 || -1) * Math.floor(Math.abs(number));
}
}
return val;
};
function clampSafeInt(number) {
return Math.min(Math.max(Number.toInteger(number), Number.MIN_SAFE_INTEGER), Number.MAX_SAFE_INTEGER);
}
// Returns a random integer between min (included) and max (included)
// Using Math.round() will give you a non-uniform distribution!
function randomInt(min, max) {
var tmp,
val;
if (arguments.length === 1) {
max = min;
min = 0;
}
min = clampSafeInt(min);
max = clampSafeInt(max);
if (min > max) {
tmp = min;
min = max;
max = tmp;
}
tmp = max - min + 1;
if (tmp > Number.MAX_SAFE_INTEGER) {
throw new RangeError('Difference of max and min is greater than Number.MAX_SAFE_INTEGER: ' + tmp);
} else {
val = Math.floor(Math.random() * tmp) + min;
}
return val;
}
console.log(randomInt(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER));
But as you can see, this is going to throw an error well before the range that I require. So I have a fiddle and come up with the following.
Number.MAX_SAFE_INTEGER = Number.MAX_SAFE_INTEGER || 9007199254740991;
Number.MIN_SAFE_INTEGER = Number.MIN_SAFE_INTEGER || -Number.MAX_SAFE_INTEGER;
Number.toInteger = Number.toInteger || function (inputArg) {
var number = +inputArg,
val = 0;
if (number === number) {
if (!number || number === Infinity || number === -Infinity) {
val = number;
} else {
val = (number > 0 || -1) * Math.floor(Math.abs(number));
}
}
return val;
};
function clampSafeInt(number) {
return Math.min(Math.max(Number.toInteger(number), Number.MIN_SAFE_INTEGER), Number.MAX_SAFE_INTEGER);
}
// Returns a random integer between min (included) and max (included)
// Using Math.round() will give you a non-uniform distribution!
function randomInt(min, max) {
var tmp,
val;
if (arguments.length === 1) {
max = min;
min = 0;
}
min = clampSafeInt(min);
max = clampSafeInt(max);
if (min > max) {
tmp = min;
min = max;
max = tmp;
}
tmp = max - min + 1;
if (tmp > Number.MAX_SAFE_INTEGER) {
if (Math.floor(Math.random() * 2)) {
val = Math.floor(Math.random() * (max - 0 + 1)) + 0;
} else {
val = Math.floor(Math.random() * (0 - min + 1)) + min;
}
} else {
val = Math.floor(Math.random() * tmp) + min;
}
return val;
}
console.log(randomInt(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER));
While we now longer throw an error, I am not sure exactly how this has effected the uniform distribution of the original MDN example (if it was uniformly distributed)?
So on I press and take a look creating Box-Muller Transform function for creating the random normally distributed range that I thought I required (but my mistake I wanted uniformly distributed). I did some reading and chose rejection sampling as the method to generate observations from a distribution. Found out how to calculate the deviation for a range without having to use Math.sqrt :
If the value of x is negative, Math.sqrt() returns NaN
This is what I came up with.
Number.MAX_SAFE_INTEGER = Number.MAX_SAFE_INTEGER || 9007199254740991;
Number.MIN_SAFE_INTEGER = Number.MIN_SAFE_INTEGER || -Number.MAX_SAFE_INTEGER;
Number.toInteger = Number.toInteger || function (inputArg) {
var number = +inputArg,
val = 0;
if (number === number) {
if (!number || number === Infinity || number === -Infinity) {
val = number;
} else {
val = (number > 0 || -1) * Math.floor(Math.abs(number));
}
}
return val;
};
function clampSafeInt(number) {
return Math.min(Math.max(Number.toInteger(number), Number.MIN_SAFE_INTEGER), Number.MAX_SAFE_INTEGER);
}
var boxMullerRandom = (function () {
var phase = 0,
RAND_MAX,
array,
random,
x1, x2, w, z;
if (crypto && crypto.getRandomValues) {
RAND_MAX = Math.pow(2, 32) - 1;
array = new Uint32Array(1);
random = function () {
crypto.getRandomValues(array);
return array[0] / RAND_MAX;
};
} else {
random = Math.random;
}
return function () {
if (!phase) {
do {
x1 = 2.0 * random() - 1.0;
x2 = 2.0 * random() - 1.0;
w = x1 * x1 + x2 * x2;
} while (w >= 1.0);
w = Math.sqrt((-2.0 * Math.log(w)) / w);
z = x1 * w;
} else {
z = x2 * w;
}
phase ^= 1;
return z;
}
}());
function rejectionSample(stdev, mean, from, to) {
var retVal;
do {
retVal = (boxMullerRandom() * stdev) + mean;
} while (retVal < from || to < retVal);
return retVal;
}
function randomInt(min, max) {
var tmp,
val;
if (arguments.length === 1) {
max = min;
min = 0;
}
min = clampSafeInt(min);
max = clampSafeInt(max);
if (min > max) {
tmp = min;
min = max;
max = tmp;
}
tmp = {};
tmp.mean = (min / 2) + (max / 2);
tmp.variance = (Math.pow(min - tmp.mean, 2) + Math.pow(max - tmp.mean, 2)) / 2;
tmp.deviation = Math.sqrt(tmp.variance);
console.log(tmp);
return Math.floor(rejectionSample(tmp.deviation, tmp.mean, min, max + 1));
}
console.log(randomInt(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER));
Not sure that I have done everything correctly (haven't broken the normal distribution), but on small integer ranges I am seeing the correct range of random integers generated.
But there is still a problem when I use the maximum limits of the range (or actually before those limits). The math still goes outside of the Number.MAX_SAFE_INTEGER value. Output from above console.log(tmp);
{mean: 0, variance: 8.112963841460666e+31, deviation: 9007199254740991}
As you can see the calculated variance is not safe. This algorithm can be ignored due to my confusion in distribution types.
So, what am I missing? Is there some simple method that I have overlooked? Must I use a big number library as the only solution?
Please put me out of my misery on this one. :)
Aucun commentaire:
Enregistrer un commentaire