Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 1 of 1
  1. #1
    Regular Coder
    Join Date
    Jun 2007
    Location
    USA
    Posts
    527
    Thanks
    26
    Thanked 74 Times in 72 Posts

    Unique Random Numbers

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

    Syntax:
    Code:
    /* 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
    Code:
    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:
    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 />"));
    Last edited by Trinithis; 12-03-2009 at 06:26 AM.
    Trinithis


 

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •