Re: [Help-bash] $RANDOM excludes value zero when called in a subscript

[Greg Wooledge]

On Tue, Aug 06, 2019 at 10:07:12PM +0200, Roger Price wrote:
> Your terminology makes me suspect that $RANDOM is of the form
> 
>  X_{n+1} = (a X_n + b) mod m
> 
> with X_0 based on (tv.tv_sec ^ tv.tv_usec ^ getpid ()) or whatever value is
> assigned to RANDOM.

Here's some of the actual code:

===========================================================================
/* Returns a pseudo-random number between 0 and 32767. */
static int
brand ()
{
  /* Minimal Standard generator 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.

     x(n+1) = 16807 * x(n) mod (2**31 - 1).

     We split up the calculations to avoid overflow.

     h = rseed / q; l = x - h * q; t = a * l - h * r
     m = 2147483647, a = 16807, q = 127773, r = 2836

     There are lots of other combinations of constants to use; look at
     
https://www.gnu.org/software/gsl/manual/html_node/Other-random-number-generators.html#Other-random-number-generators
 */

  bits32_t h, l, t;


  /* Can't seed with 0. */
  if (rseed == 0)
    rseed = 123459876;
  h = rseed / 127773;
  l = rseed - (127773 * h);
  t = 16807 * l - 2836 * h;
  rseed = (t < 0) ? t + 0x7fffffff : t;

  return ((unsigned int)(rseed & BASH_RAND_MAX));       /* was % 
BASH_RAND_MAX+1 */
}

/* Set the random number generator seed to SEED. */
static void
sbrand (seed)
     unsigned long seed;
{
  rseed = seed;
  last_random_value = 0;
}

static void
seedrand ()
{
  struct timeval tv;
  SHELL_VAR *v;

  gettimeofday (&tv, NULL);
#if 0
  v = find_variable ("BASH_VERSION");
  sbrand (tv.tv_sec ^ tv.tv_usec ^ getpid () ^ ((u_bits32_t)&v & 0x7fffffff));
#else
  sbrand (tv.tv_sec ^ tv.tv_usec ^ getpid ());
#endif
}

[[ SNIP ]]

int
get_random_number ()
{
  int rv, pid;

  /* Reset for command and process substitution. */
  pid = getpid ();
  if (subshell_environment && seeded_subshell != pid)
    {
      seedrand ();
      seeded_subshell = pid;
    }

  do
    rv = brand ();
  while (rv == last_random_value);
  return rv;
}

static SHELL_VAR *
get_random (var)
     SHELL_VAR *var;
{
  int rv;
  char *p;

  rv = get_random_number ();
  last_random_value = rv;
  p = itos (rv);

  FREE (value_cell (var));

  VSETATTR (var, att_integer);
  var_setvalue (var, p);
  return (var);
}
===========================================================================

> I reduced my test script to one single use of $RANDOM and still saw the same
> anomaly, so it's not caused by multiple instances.

I'm not getting through.

You keep running a NEW instance of bash, a NEW script, what you call a
"sub-script".  This restarts a brand new instance of the bash PRNG.

You are always getting the FIRST result from this newborn PRNG, never
a second, third, tenth, one-thousandth result.

Only the first result.

The "single use of $RANDOM" is precisely the PROBLEM.

You want the opposite of a "single use of $RANDOM".  You want to call
$RANDOM a whole crapload of times in a single process.


> I read your message carefully, several times, but I see no explanation for
> why $RANDOM does not issue zero values from a sub-script.

The first few values from a newborn PRNG are not very random.  I said
this last time.

Do you see the last_random_value variable in the code above?  It's set
to 0 when the PRNG is seeded.  And in get_random_number() rv is rejected
and re-rolled as long as it's equal to last_random_value.

You can't get 0 as the FIRST result from the bash PRNG.  Because the
last_random_value variable is set to 0 at that point, and 0 is therefore
rejected.

You're only ever getting the FIRST result because you keep respawning
a brand new PRNG for every. single. random. value. you. get.

The first few values from a PRNG are not as good as later values.
You want ONE instance of the PRNG to keep churning out numbers for
a while.

If you run a "sub-script" (or just a "script", because that's what it
really is) and only get ONE value from $RANDOM, it won't be very random.
That's the nature of the PRNG.

That's why I gave you my three rules last time.

Redesign your project in such a way that it gets ALL of its random
numbers from a single PRNG.  Not a brand new "sub-script" every time
you want another random number.