Unique Random Numbers

[Trinithis]

Unique.js allows one to construct space efficient generators of unique random numbers without compromising their distributions.

Syntax:

/* Creates new Unique generator.
 * If x not supplied, x is assumed to be 1e4 (which is 10000).
 * Guarantees at least x unique numbers can be generated.
 * The exact amount is ceil (log10 (max (x, 0)))
 */
var unique = new Unique (x);

/* Returns random number or null if it cannot generate any more random numbers.
 * Returned numbers are a subset of those returned by Math.random ().
 */
unique.random ();

/* Returns false if and only if unique.random () will return null.
 */
unique.hasRandom ();

/* Guarantees y will not be returned by unique.random ().
 * May consume a random number from the generator.
 * y must satisfy 0 <= y < 1.
 */
unique.add (y);

Unique.js

function Unique (numberOfDistinctValues) {
  if (numberOfDistinctValues === undefined) {
    numberOfDistinctValues = 1e4;
  }
  if (numberOfDistinctValues < 0) {
    numberOfDistinctValues = 0;
  }
  var numDigits = Math.ceil (Math.log (numberOfDistinctValues) / Math.log (10));
  var maxDigitLength = 15;
  if (numDigits > maxDigitLength) {
    numDigits = maxDigitLength;
  }
  var offset = maxDigitLength - numDigits;
  this.hash = Unique.mkHash (numDigits, offset);
  this.unusedBitCount = Math.pow (10, numDigits);
  this.bitmap = new Bitmap ();
}

Unique.mkHash = function (numDigits, offset) {
  return function (num) {
    var mult = Math.pow (10, numDigits + offset);
    var mod = Math.pow (10, numDigits);
    return Math.floor (num * mult % mod);
  };
};

Unique.prototype = {
  
    constructor: Unique

  , toString: function () {
      return "[object Unique]";
    }

  , hasRandom: function () {
      return this.unusedBitCount > 0;
    }

  , add: function (num) {
      this.bitmap.set (this.hash (num));
    }

  , random: function () {
      if (this.unusedBitCount <= 0) {
        return null;
      }
      while (true) {
        var rand = Math.random ();
        var hashed = this.hash (rand);
        if (!this.bitmap.get (hashed)) {
          this.bitmap.set (hashed);
          --this.unusedBitCount;
          return rand
        }
      }
    }
};

function Bitmap () {
  this.arr = [];
}

Bitmap.prototype = {

    constructor: Bitmap

  , clear: function (i) {
      var pos = Math.floor (i / 32);
      this.arr [pos] = this.arr [pos] & ~(1 << i % 32);
    }

  , get: function (i) {
      return (this.arr [Math.floor (i / 32)] & 1 << i % 32) > 0;
    }

  , set: function (i) {
      var pos = Math.floor (i / 32);
      this.arr [pos] = this.arr [pos] | 1 << i % 32;
    }

  , toString: function () {
      return "[object Bitmap]";
    }
};

Example Code:

function println (x) {
  document.write (x + "<br />");
}

var unique = new Unique (1e1);

var rands = []

while (unique.hasRandom ()) {
  rands.push (unique.random ());
}

rands.sort ();

println (rands.length);
println ("");
println (rands.join ("<br />"));