Re: bad random numbers

[John W. Eaton]

On 14-Jul-1999, Jim Van Zandt <address@hidden> wrote:

| 
| >   > I think it would be good to have Bill Lash's code incorporated
| >   > in the standard octave source.  I'm assuming it does what it's
| >   > supposed to do and won't cause problems on other systems.
| >   > 
| >
| >   If John wants to incorporate the patch, that is fine by me, but
| >   remember that it was a quick hack, and that it does have some
| >   limitations.
| 
| I second someone else's suggestion that /dev/urandom be used where
| available (Linux only, AFAIK).  Second choice would be gettimeofday(),
| and third choice would be time().

OK, I will `fix' this for 2.1.x by using /dev/urandom if it is
availble, then something based on gettimeofday, then time.  Using
/dev/urandom should not be too hard, but I'd like suggestions for what
to do to compute the seed given a value returned from getttimeofday or
time (see below).

I will also add a note to the manual stating that although Octave
tries to create a different seed for the random number generator each
time it starts, there is no guarantee that the sequence of seeds or
the sequence of initial values returned by the random number generator
has any special properties.

The current code for computing the two initial seeds used by the
generator looks something like this:

  time_t now;
  struct tm *tm;
 
  time (&now);
  tm = localtime (&now);
 
  int hour = tm->tm_hour + 1;
  int minute = tm->tm_min + 1;
  int second = tm->tm_sec + 1;

  int s0 = tm->tm_mday * hour * minute * second;
  int s1 = hour * minute * second;

  s0 = force_to_fit_range (s0, 1, 2147483563);
  s1 = force_to_fit_range (s1, 1, 2147483399);

In other words, as I write this, s0 would be 14*12*53*11, or 97944 and
s1 would be 6996.  The reason for doing the multiplication was to
keep the seeds from simply increasing for each call, but it may not
help very much.  As I look at it now, the two biggest problems that I
see with this code are

  1. During a given month, the range of s1 is at most [1, 2678400] and
     the range of s2 is [1, 86400].  Obviously, this doesn't come
     close to approaching the range of allowable seeds (given in the
     arguments to force_to_fit_range above) so it could definitely be
     improved.  Mulitplying by a constant would help spread out the
     bits, but it would leave a lot of gaps.

  2. The seed doesn't change if Octave is called twice within the same
     second.  FWIW, I don't see this as a really big problem, because
     Octave is typically used as an interactive tool, or at least to
     solve problems that take more than one second to execute.  But,
     since it is easy to avoid this problem on most systems, it might
     as well be fixed.

Simply taking the value of tv->sec + tv->usec as a double and
splitting it into two ints (the method used by Bill Lash's patch) also
has the problem of not spanning the range of possible seeds.  The
high-order bits (sign, exponent, and the first 20 bits of the mantissa
on a system that uses the IEEE floating point format) of that number
are likely to stay the same over many calls.

So, for systems that don't have /dev/urandom, it would be good to have
a method of computing the seed that distributes these bits in some
`random' way so that they uniformly span the range of possible values
for the seed.  Does anyone have any good ideas for how to do this?

Things like process id or the address of a variable are probably not
very good because on sequential runs, the address can end up being the
same and the process id may only increase by one or two.

jwe



---------------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.  To ensure
that development continues, see www.che.wisc.edu/octave/giftform.html
Instructions for unsubscribing: www.che.wisc.edu/octave/archive.html
---------------------------------------------------------------------