3 ms·
This is not a uniform distribution: const randIntRange = (i, j, engine = defaultEngine) => { const min = Math.ceil(i) const max = Math.floor(j)
by vore 3y ago
This is not a uniform distribution:
const randIntRange = (i, j, engine = defaultEngine) => {
const min = Math.ceil(i)
const max = Math.floor(j)
return Math.floor(engine() * (max - min + 1)) + min
}
If you assume engine() outputs, say, 64 bits of entropy, any number range that is not an even factor of 2^64 will exhibit intermittent bias where the numbers are rounded.
The only correct way to do this is to do rejection sampling: generate an integer x with log2(max - min) bits and if x >= max - min retry until you do:
function randBelow(n) {
const nbits = Math.ceil(Math.log2(n));
while (true) {
const x = getRandBits(nbits);
if (x < n) { return x; }
}
}
function randIntHalfOpenRange(min, max) {
return min + randBelow(max - min);
}
function randIntRange(min, max) {
return randIntHalfOpenRange(min, max + 1);
}
The primitive you want for building distributions on is not to generate a floating point number between 0.0 and 1.0, but to generate an integer of at most x bits.
- vore 3y agoAdditionally, the shuffle function (sequence.js) has quadratic complexity due to repeated copying of the input array. You could get a vast performance improvement by copying the input array and running the standard Fisher–Yates shuffle over it: it will both run in linear time and will not thrash cache as much.
- chriscavs 3y agothanks for bringing this to my attention, I will be sure to check this out
- chriscavs 3y agoThank you for the comment! I am aware of this issue, and am working to address in v1.1.0. The context you provide here is very helpful for me. I've opened an issue on github for this: https://github.com/ChrisCavs/aimless.js/issues/2 https://github.com/ChrisCavs/aimless.js/issues/2