Skip to content

randIntRange non-uniform distribution #2

@ChrisCavs

Description

@ChrisCavs

Based on comments from HN and Reddit:

  • Math.floor(engine() * (max - min + 1)) + min creates bias, since the engine output bits do not divide evenly into the range
  • replace with rejection sampling

from vore on HN:

  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);
  }

Metadata

Metadata

Assignees

Projects

No projects

Relationships

None yet

Development

No branches or pull requests

Issue actions