[mythtv] MythMusic playlists still not intelligent enough IMHO

[Poul Petersen]

> 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.

	Very fun stuff. A "mixed" LCG to use your terminology is generally
a perfect choice for these kinds of applications because if chosen with a little
care it will appear sufficiently random to a human. Moreover, if the coefficients
are chosen carefully, then you can ensure that the period of the generator will
be n-1 for any modulus n (where n is the number of songs as well, counting from
0). To ensure that you get a full period generator, you need to choose:

LCG: x'=(a*x+b) mod n

1) b and n must be relatively prime (no common factors)

2) a-1 must be divisible by all prime factors of n

3) if 4 divides n, then 4 must divide a-1.

  Given a generic value of n, the most painful part of this calculation is
probably #2, since you must factor n. It's unlikely that many people have 
a song list with so many songs as to make this calculation infeasable, on
modern hardware. Rather, it's just that no one may want to code up a 
factoring algorithm just for this application.

  Here is where we can combine ideas though. For a given song list length
"s", choose n=2^k such that n>s but (n/2)<s. That is, let n be the first
power of 2 larger than s. Now choosing b is easy since any odd integer
will be relatively prime to a power of 2:

  b=2*rand(n/4 .. n/2-1)+1	(*assuming n>4)

  Here I've choosen b so that it is an odd integer (2k+1) in the range
n/2 to n-1. Choosing a value for b in the upper end of the ring ensures
better "mixing". 

  Choosing a is also pretty easy. The only prime factor of n is 2, so
a=2l+1. Adding constraint #3 is also easy. If n>4 then we know 4 divides n,
so a=4p+1. Essentially, we need only ensure that 2 and 4 both divide
a-1. So,

  a=4*rand(n/8 .. n/4-1)+1 	(*assuming n>8)

  Again, I've forced a to be "large" which is not necessary but will probably
create better "mixing". Now you have "random" coefficients for a full period
PNG where n is only slight larger than s. As previously suggested, just
discard any values that fall between s and n:

choose a starting point randomly x0 in [0 .. n-1]
iterate x'=a*x+b mod n
if x' in [ 0 .. s-1 ] play x'
otherwise iterate again.
if x'=x0 re-generate coefficients

*Note: There are some edge effects that would need to be accounted for for
really small playlists s=1 thru s=8, such that n=8 or 4 or 2. It's not hard to
fix I just didn't bother to write it down.

-poul