Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is the bash function $RANDOM supposed to have an uniform distribution?

I understand that the bash function $RANDOM generates random integer number within a range, but, are these number supposed to follow (or approximate) an uniform discrete distribution?

like image 709
papirrin Avatar asked Apr 11 '13 01:04

papirrin


2 Answers

I just printed $RANDOM a million times, turned it into a histogram, and viewed it with gnumeric, and the graph shows a very Normal distribution!

for n in `seq 1 1000000`; do echo $RANDOM ; done > random.txt
gawk '{b=int($1/100);a[b]++};END{for (n in a) {print n","a[n]}}' random.txt > hist.csv
gnumeric hist.csv

So, if you want an approximately linear distribution, use $(( $RANDOM % $MAXIMUM )) and don't use it with $MAXIMUM larger than 16383, or 8192 to be safe. You could concatenate $RANDOM % 1000 several times if you want really large numbers, as long as you take care of leading zeros.

If you do want a normal distribution, use $(( $RANGE * $RANDOM / 32767 + $MINIMUM)), and remember this is only integer math.

like image 111
PFudd Avatar answered Sep 18 '22 23:09

PFudd


The Bash document doesn't actually say so:

RANDOM

Each time this parameter is referenced, a random integer between 0 and 32767 is generated. Assigning a value to this variable seeds the random number generator.

Reading that, I would certainly assume that it's intended to be linear; it wouldn't make much sense IMHO for it to be anything else.

But looking at the bash source code, the implementation of $RANDOM is intended to produce a linear distribution (this is from variable.c in the bash 4.2 source):

/* The random number seed.  You can change this by setting RANDOM. */
static unsigned long rseed = 1;
static int last_random_value;
static int seeded_subshell = 0;

/* A linear congruential random number generator based on the example
   one in the ANSI C standard.  This one isn't very good, but a more
   complicated one is overkill. */

/* Returns a pseudo-random number between 0 and 32767. */
static int
brand ()
{
  /* From "Random number generators: good ones are hard to find",
     Park and Miller, Communications of the ACM, vol. 31, no. 10,
     October 1988, p. 1195. filtered through FreeBSD */
  long h, l;

  /* Can't seed with 0. */
  if (rseed == 0)
    rseed = 123459876;
  h = rseed / 127773;
  l = rseed % 127773;
  rseed = 16807 * l - 2836 * h;
#if 0
  if (rseed < 0)
    rseed += 0x7fffffff;
#endif
  return ((unsigned int)(rseed & 32767));       /* was % 32768 */
}

As the comments imply, if you want good random numbers, use something else.

like image 22
Keith Thompson Avatar answered Sep 19 '22 23:09

Keith Thompson