[vox-tech] random number question

[vox-tech@lists.lugod.org]

On Wed, May 15, 2002 at 11:44:21AM -0700, Mark K. Kim wrote:
> On Wed, 15 May 2002 msimons@moria.simons-clan.com wrote:
> >   These algorithms also tend to "cycle" back upon themselves, so
> > if they spit out (10, 5, 8, 20, ...) sometime millions of reads
> > later the same millions of numbers will be pulled in the same order.
> 
> If you look at the textbook random number generator (which reminds me of a
> story... I'll tell you in a bit), you realize you can actually make a very
> good use of this idea.  For example, if you want to play all the songs on
> your CD (or MP3 library, or whatever) all exactly once in random order
> before playing the same song again (so you don't get the same song playing
> twice in a row), you can simply manipulate the random number generator
> slightly to do that.  It can be very useful, but unfortunately not many
> programs use this technique.

  If your goal is play each song once in a random order, I don't see why
you don't just assign each song a random number, then sort the list 
of songs by those random numbers to get the play list order.  When the 
first play-songs pass is finished you could generate new numbers for the 
songs and resort... very simple and easy to code.  (*)


*: if you have a sufficiently large amount of music (say 12 hours worth)
   it's unlikely a person will notice reuse of the list for the first 
   week or so... so you could skip that reordering step.


> >   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.
> 
> It generates the numbers in the same sequence with the algorithm I'm
> thinking about, but I'm sure there are better algorithms implemented in
> the C library.  It's simple enough to detect a cycle and reseed the random
> number generator, anyway.

  I'm not sure that detecting a cycle is simple... if the first three
numbers you pulled from the random number function are 13, 22, 5.  It
does not mean that you have found a cycle the next time those numbers
show up in that order... depending on the algorithm a the set of numbers
could be hit X times, and there is always a chance that 13, 22, and 5
will be hit a second time in that order without a cycle having happened.

from random(3)
# The random() function uses a non-linear additive  feedback random  number
# generator employing a default table of size 31 long integers to return
# successive  pseudo-random  numbers  in the range from 0 to RAND_MAX.
# The period of this random  number  generator  is  very  large,
# approximately 16*((2**31)-1).

The default period is ... 34359738352

/usr/include/stdlib.h:#define   RAND_MAX        2147483647

so every number will be seen 16 times before a cycle has really happened.

btw: with the random(3) interface you can change the size of the state
tables, which I suspect enlarges the number of pulls that can be done
before it cycles.  See man page for details.

> BTW, some people like to seed the algorithm before every generation of
> random number.  Something about being more random...

  I don't understand how this could be "more random"... in effect they 
are just applying a hash function to whatever they use as their seed.

  TTFN,
    Mike