randomprobabilitydiscrete-mathematicsprngprobability-density

Keep uniform distribution after remapping to a new range


Since this is about remapping a uniform distribution to another with a different range, this is not a PHP question specifically although I am using PHP.

I have a cryptographicaly secure random number generator that gives me evenly distributed integers (uniform discrete distribution) between 0 and PHP_INT_MAX.

How do I remap these results to fit into a different range in an efficient manner?

Currently I am using $mappedRandomNumber = $randomNumber % ($range + 1) + $min where $range = $max - $min, but that obvioulsy doesn't work since the first PHP_INT_MAX%$range integers from the range have a higher chance to be picked, breaking the uniformity of the distribution.


Solution

  • This is what I ended up doing. PRNG 101 (if it does not fit, ignore and generate again). Not very sophisticated, but simple:

    public function rand($min = 0, $max = null){
    
      // pow(2,$numBits-1) calculated as (pow(2,$numBits-2)-1) + pow(2,$numBits-2) 
      // to avoid overflow when $numBits is the number of bits of PHP_INT_MAX
      $maxSafe = (int) floor(
        ((pow(2,8*$this->intByteCount-2)-1) + pow(2,8*$this->intByteCount-2))   
        / 
        ($max - $min)
      ) * ($max - $min);
    
      // discards anything above the last interval N * {0 .. max - min -1} 
      // that fits in {0 ..  2^(intBitCount-1)-1}
      do {
        $chars = $this->getRandomBytesString($this->intByteCount);
        $n = 0;
        for ($i=0;$i<$this->intByteCount;$i++) {$n|=(ord($chars[$i])<<(8*($this->intByteCount-$i-1)));}
      } while (abs($n)>$maxSafe);
    
      return (abs($n)%($max-$min+1))+$min;
    
    }
    

    Any improvements are welcomed.

    (Full code on https://github.com/elcodedocle/cryptosecureprng/blob/master/CryptoSecurePRNG.php)