[mythtv] MythMusic playlists still not intelligent enough IMHO

[Chris Hamilton]

> On 4/19/07, Eskil Heyn Olsen <myth at eskil.org> wrote:
>> On Wed, 2007-04-18 at 10:50 -0400, Dan Wilga wrote:
>>
>>> - choose the index of the first song, S, randomly:  S = rand() % N
>>> - afterward, each new song, S' is calculated like so:  S' = (S + P) % N
>>>
>>> A mathematics guru friend of mine sent me the proof that this
>>> sequence is guaranteed to visit each song exactly once, in a
>>> pseudorandom order. It also has the advantage that the sequence is
>> After looking at this, it seems that the pseudorandom order is just
>> continuously adding P % N to S and wrapping at N. So essentially, let N
>> be 50, P be 15485863 (big prime) and S0 be 20.
>>
>>  S1 = (20 + 15485863) % 50 = 33
>>  S2 = (33 + 15485863) % 50 = 46
>>  S3 = (46 + 15485863) % 50 = 9
>>  S4 = (9 + 15485863) % 50 = 22
>>
>> essentially you just add 13 (15485863 % 50) every time. That seems sub
>> pseudorandom to me. It even seems that the only reason you need a prime
>> is to ensure that P % N isn't 0.
>>
>> Or did I (again) brainfart on something ?
>>
>> eskil
> 
> You are correct, eskil. a+b (mod n) = (a (mod n) + b (mod n)) (mod n).
> Each song will be chosen exactly once, but not in a very random way.
> Furthermore if P is chosen at compile time then the same order is used
> if N does not change. The rand() only changes the starting point in
> the sequence.

The above is a simple Linear Congruential (Pseudo-)Random Number
Generator, and they are known for being cheap and quick, but with not
terribly random results.  The higher order bits are fairly random, but
the lower order bits are not. In fact, for the example you worked
through above, the numbers will alternate between being odd and even all
along, showing that the least significant bit has an absurdly small period.

However, in the context of shuffling music, this isn't too bad. Such
RNGs have been used for a long time in many applications, and there's a
good chance this is exactly what's under the hood in most MP3 device
shuffle modes.

Another option is to use a slightly stronger number generator with a
period just greater than the number of songs in the playlist (something
like a multiple recursive linear generator).  There are in fact fairly
high quality versions of these with various periods. One could imagine
choosing ~32 such generators with (prime) periods p_i roughly near 2^i
for b=1..32. Then, for a playlist of length i choose the smallest p_i >
i, and use that generator.  The generator will occasionally (with no
more than 50% chance assuming the p_i are well chosen) choose numbers >
n, but these can simply be skipped until it produces a number in the
range 1..n.  Again, only the index of the last played song in the
playlist need be stored for the random number generator to continue
without repeats.

> I have not followed the discussion, but why not simply create an array
> [0,1,2,...,N-1] and shuffle this using STL's random_shuffle?
> 
> A playlist containing 32,000 songs results in a 1MB array, is that
> really too large?
> 
> If it is, then the algorithm used in random_sample could be used to
> select e.g. 1000 unique songs at random. When this list has been
> played, select 1000 new unique songs (possibly some of those from the
> first sample, but after 1000 songs one should not care?)

Explicitly storing an array of indices does seem a little wasteful when
there are alternative methods of achieving the same results that don't
require near as much storage space.

Regards,

Chris