tools/etc/rand

   1 #!/usr/bin/env bash
   2 #
   3 # Generates a random integer in a given range
   4 # http://unix.stackexchange.com/questions/157250/how-to-efficiently-generate-large-uniformly-distributed-random-integers-in-bas/157837#157837
   5
   6 # computes the ceiling of log2
   7 # i.e., for parameter x returns the lowest integer l such that 2**l >= x
   8 log2() {
   9   local x=$1 n=1 l=0
  10   while (( x>n && n>0 ))
  11   do
  12     let n*=2 l++
  13   done
  14   echo $l
  15 }
  16
  17 # uses $RANDOM to generate an n-bit random bitstring uniformly at random
  18 #  (if we assume $RANDOM is uniformly distributed)
  19 # takes the length n of the bitstring as parameter, n can be up to 60 bits
  20 get_n_rand_bits() {
  21   local n=$1 rnd=$RANDOM rnd_bitlen=15
  22   while (( rnd_bitlen < n ))
  23   do
  24     rnd=$(( rnd<<15|$RANDOM ))
  25     let rnd_bitlen+=15
  26   done
  27   echo $(( rnd>>(rnd_bitlen-n) ))
  28 }
  29
  30 # alternative implementation of get_n_rand_bits:
  31 # uses /dev/urandom to generate an n-bit random bitstring uniformly at random
  32 #  (if we assume /dev/urandom is uniformly distributed)
  33 # takes the length n of the bitstring as parameter, n can be up to 56 bits
  34 get_n_rand_bits_alt() {
  35   local n=$1
  36   local nb_bytes=$(( (n+7)/8 ))
  37   local rnd=$(od --read-bytes=$nb_bytes --address-radix=n --format=uL /dev/urandom | tr --delete " ")
  38   echo $(( rnd>>(nb_bytes*8-n) ))
  39 }
  40
  41 # for parameter max, generates an integer in the range {0..max} uniformly at random
  42 # max can be an arbitrary integer, needs not be a power of 2
  43 rand() {
  44   local rnd max=$1
  45   # get number of bits needed to represent $max
  46   local bitlen=$(log2 $((max+1)))
  47   while
  48     # could use get_n_rand_bits_alt instead if /dev/urandom is preferred over $RANDOM
  49     rnd=$(get_n_rand_bits $bitlen)
  50     (( rnd > max ))
  51   do :
  52   done
  53   echo $rnd
  54 }
  55
  56 # MAIN SCRIPT
  57
  58 # check number of parameters
  59 if (( $# != 1 && $# != 2 ))
  60 then
  61   cat <<EOF 1>&2
  62 Usage: $(basename $0) [min] max
  63
  64 Returns an integer distributed uniformly at random in the range {min..max}
  65 min defaults to 0
  66 (max - min) can be up to 2**60-1
  67 EOF
  68   exit 1
  69 fi
  70
  71 # If we have one parameter, set min to 0 and max to $1
  72 # If we have two parameters, set min to $1 and max to $2
  73 max=0
  74 while (( $# > 0 ))
  75 do
  76   min=$max
  77   max=$1
  78   shift
  79 done
  80
  81 # ensure that min <= max
  82 if (( min > max ))
  83 then
  84   echo "$(basename $0): error: min is greater than max" 1>&2
  85   exit 1
  86 fi
  87
  88 # need absolute value of diff since min (and also max) may be negative
  89 diff=$((max-min)) && diff=${diff#-}
  90
  91 echo $(( $(rand $diff) + min ))