[vox-tech] random number question

[Jeff Newmiller]

On Wed, 15 May 2002, Mark K. Kim wrote:

> On Wed, 15 May 2002 msimons@moria.simons-clan.com wrote:
> 
> >   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.  (*)
> 
> Using the above technique, you'd have to account for situations when you
> generate two same random numbers.  My method works out the math in such a
> way that all numbers are unique.  Not only that, you end up with numbers
> exactly between 0 and N-1, where N-1 is the number of songs, which is
> neat-o from the academic point of view.

We are referring to linear congruential generators, right? as in,

   r_next = (p * r_last + q) % m

I am not aware of an "easy" way to determine what "N" is, given p, q, and
m. (Note that N is unlikely to be equal to m, because as soon as the
algorithm hits a number it has already generated, the sequence will
repeat.)  If you preselect those values, then N becomes predetermined.  
If you want N to correspond to the actual number of songs in a list,
determining those values at runtime becomes much more computationally
intensive than either Mike's method, or the standard "shuffle" algorithm
(iteratively pick randomly chosen songs from the unselected list of songs
until all songs have been selected).

> 
> >   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.
> 
> For most random number generating algorithm, you can easily calculate how
> many calls it takes to end up in a cycle (ie - INT_MAX).  Given that
> information, you can keep track of how many random number requests were
> made to see when the cycle will restart.

We must be referring to different algorithms.  Care to share?

---------------------------------------------------------------------------
Jeff Newmiller                        The     .....       .....  Go Live...
DCN:<jdnewmil@dcn.davis.ca.us>        Basics: ##.#.       ##.#.  Live Go...
                                      Live:   OO#.. Dead: OO#..  Playing
Research Engineer (Solar/Batteries            O.O#.       #.O#.  with
/Software/Embedded Controllers)               .OO#.       .OO#.  rocks...2k
---------------------------------------------------------------------------