[vox-tech] random number question

[vox-tech@lists.lugod.org]

On Wed, May 15, 2002 at 11:49:52AM -0700, Jeff Newmiller wrote:
> On Wed, 15 May 2002 msimons@moria.simons-clan.com wrote:
> >   I think each sequence is completely independent of the others...
> > in that the order of numbers in one cycle of all sequences will be
> > different.
> 
> Not quite sure I understand what you are saying here.  If you find
> yourself at a particular point in the cycle, the numbers that follow are
> predetermined. The problem is that the "cycle" for a good pseudo-random
> number generator is often much longer than can be represented by the seed
> value, so you may not have complete flexibility to choose where in the
> cycle you will start.  A good seeding algorithm will distribute the
> starting points throughout the cycle, so that each seed will appear to
> yield a different sequence.  A bad one could assign multiple seed values
> to the same points in the cycle. :)

Jeff,

  I'm not sure that this is correct, this is what I think happens...

  I think that there are X different cycles, not one cycle that the
seed defines an initial offset into.  I'm not certain of this... so 
if you know otherwise let me know and I'll stop thinking that.  ;)

    Later,
      Mike

ps: I do understand that algorithms where all seeds share a common cycle
    just start at different offsets in it, exist and are easy to come up
    with... I thought that the real rand functions don't have that property.


to phrase what I'm thinking a few other ways:

what I was what I was trying to say there is...
- there is a completely different number sequence for each seed
- no two seeds cover the numbers in the same orders even if you shift
  the numbers in a cycle around.
- if you pretend that all the numbers in a cycle are one big loop or 
  ring of numbers.  and you pull the loop for seed 1, and the loop for
  seed 2, you will not be able to "spin" the loops around to have them
  match number for number.
- if you find a place in seed 1's list that gives (4, 12, 32) and you find
  a place in seed 2's list that gives (4, 12, 32)... if start pulling one
  number from both lists they will not continue to be the same.


  to phrase another way... the following is an example of how I 
think the rand/random functions do _not_ operate.


  pretend I designed a pseudo-random number generator that returns
numbers from 0 to 16.  It uses the following static table of numbers,
the seed sets the starting position in the array, when a random number
is returned the next_value index is incremented and wraps to zero when
16... like the following:
=============
#define MY_MAX_RAND 16

static int data_table[] = {
  2, 5, 1, 12, 14, 6, 7, 4, 15, 8, 9, 10, 13, 11, 3, 16
};
static unsigned char next_value = 1;

int dumb_random()
{
  int result = data_table[next_value];
  next_value = next_value == 16 ? 0 : next_value++;
  return result;
}

int dump_srandom(int seed)
{
  next_value = seed % (MY_MAX_RAND + 1);
}
=============


  To build on the stuff above, how I think things do work is something
like:
static int master_data_table[][] = {
  { 2, 5, 1, 12, 14, 6, 7, 4, 15, 8, 9, 10, 13, 11, 3, 16 },
  { 6, 7, 4, 2, 14, 15, 8, 9, 10, 13, 5, 3, 16, 1, 12, 11 },
  /* a bunch more arrays with completely different orders */
};
static int *data_table = master_data_table[1];
static unsigned char next_value = 1;

int dump_srandom(int seed)
{
  data_table = master_data_table[seed];
  next_value = 1;
}
=============