[mythtv] MythMusic playlists still not intelligent enough IMHO
Chris Hamilton
chamilton at cs.dal.ca
Thu Apr 19 12:52:58 UTC 2007
Lasse Nisted wrote:
> I think a linear congruential pseudo random number generator should involve
> a multiplication
> (See e.g. http://en.wikipedia.org/wiki/Linear_congruential_generator )
> Though, in that wiki A is allowed to be 1. But then, as eskil points
> out, it's just
> "add P % N".
A mixed linear congruential generator has both the add and the multiply,
whereas an additive LCG uses a = 1 (which is what is going on here).
Similarly, a multiplicative LCG uses b = 0.
> The problem with more sophisticated RNGs are that some value in
> [0..N-1) might be generated twice before having exhausted the entire interval.
> (Or am I wrong at that point?)
> This was what Dan tried to avoid.
Any RNG will have some finite period p. Assuming the RNG was well setup
it will iterate through all values 0..p-1 or 1..p-1 exactly once each
before repeating its period. So, choosing an RNG with a period p
greater than n (the number of songs), you can simply discard values that
lie outside of the range 1..n until you land an a value within the
range. This is only practical if p isn't too much larger than n.
The built in RNG in any OS is likely to have a very large period,
effectively as large as the machine word size. The problem with using
that for selecting values in 1..n is that *most* of the values will lie
outside of the range 1..n. Thus, some other mapping is applied to bring
the values into that range (dividing by RANDMAX/n, or taking the value
mod n). These mappings then make it very likely that certain values in
the range 1..n will be visited multiple times before the entire range is
exhausted, which is the cause of current problems.
Chris
More information about the mythtv-dev
mailing list