what is "True random shuffle "

[MarkGaleck]

The Wikipedia article about Rockbox says it has the feature "True random shuffle".  Anybody knows whether this statement has meaning?  For example, what could "true" mean?  It is not possible to have a theoretically mathematically random shuffle in a deterministic device, is it?  Or is the "randomness" work much better than the original firmware(s)? 

Thank you

[Llorean]

For example, the iRiver "shuffle" feature, when provided the same list of songs, played them in the exact same "shuffled" order each time. Rockbox has a good pseudorandom function, and generates a fresh randomly shuffled playlist every time you launch a playlist in shuffled mode, or every time a playlist repeats with the shuffle-on-repeat feature enabled.

[Eriol]

For example, the iRiver "shuffle" feature, when provided the same list of songs, played them in the exact same "shuffled" order each time. Rockbox has a good pseudorandom function, and generates a fresh randomly shuffled playlist every time you launch a playlist in shuffled mode, or every time a playlist repeats with the shuffle-on-repeat feature enabled.

For any player with a clock you'd think this'd be pretty trivial to do (I know my X5 has one at least), just re-seed the rand() function with the current time every time you do the re-shuffle.

For ones without a clock... re-feed the current shuffle's output into the randomness function (not exactly random, but possible if you keep a running copy of the "last random" sequence, or some representation to feed back into a generator)?  Read in some noise from a microphone/line in if either exists (very random)?  Time (clock tics) between button presses perhaps (the user input itself causes the randomness, which should be pretty random, and good for a user-centric devices like for this purpose)?

What's being done now?  I'm curious. 

[RotAtoR]

What's being done now?  I'm curious. 

It's general practice to seed it with the current (processor) clock tick, which for all devices so far is 1/100ths of seconds since rockbox was booted. A RTC is not necessary at all.

[bk]

I wrote that line in the article. Llorean is correct, it refers to the fact that Rockbox shuffle is much more 'random' than iriver fw shuffle (back when I wrote it the iriver port was the only functional non-Archos port).

[riksweeney]

It's general practice to seed it with the current (processor) clock tick, which for all devices so far is 1/100ths of seconds since rockbox was booted. A RTC is not necessary at all.

That's quite a cool idea, I was wondering how Rockbox did randomness on players without a clock.

[ryran]

Ya know... am I the only one who would really love to have the option of a not-somuch-true-random, i.e. intelligent, shuffle? I love to create on-the-fly playlists of a handful to a dozen albums by different artists and have always thought it would be awesome if I could tell RB to shuffle the list in such a way that no two consecutive songs are from the same artist (or album).

That would rock. Perhaps I'll fill out a feature request.

[soap]

Ya know... am I the only one who would really love to have the option of a not-somuch-true-random, i.e. intelligent, shuffle? I love to create on-the-fly playlists of a handful to a dozen albums by different artists and have always thought it would be awesome if I could tell RB to shuffle the list in such a way that no two consecutive songs are from the same artist (or album).

That would rock. Perhaps I'll fill out a feature request.

Foobar2000 has a pluggin (Shuffle) that does this in a very nice manner.  It allows you to set three variables.
1 - What percentage of the playlist to play before a repeat is allowed.
2 - What tag(s) to watch for when shuffling (example:  -album|+genre would shuffle to a different album, but same genre.  Leaving the field blank puts no restraint on the shuffle at all)
3 - A minimum and maximum distance from the last track the randomizer is allowed to jump.

Just thought I would throw that in there...

[afruff23]

Actually no PRNG is actually random. Rockbox uses a Mersenne Twister(look in FAQ). Mersenne Twisters have a periodicity of  2^19937 − 1. Read
http://en.wikipedia.org/wiki/Mersenne_Twister
 for more info. After a while(a VERY LONG while), you will begin to notice repeating.

[bk]

...where "a VERY LONG while" (if you change songs once per second) is a period of time many, many, many orders of magnitude greater than the age of the known universe.

Plug 2^19937 into a computer calculator with a sufficient output (bc on unix/linux works) to see how huge it is.

[Yotto]

Yeah but this is 2^19937... MINUS ONE.

However, pseudorandom vs random is an old topic. Nobody will notice that it's not random, as opposed to some truly horiffic "random" schemes I've seen in players.  I had a CD-MP3 player whose random mode was to take every prime number and run doubles of it up to 64, then pick the next prime number.  I have no idea who decided to do it that way when a very simple RNG would be both better for the end user and easier to code, but there it was.

I'm serious.  I played tracks 2, 4, 8, 16, 32, 64, 3, 6, 12, 24, 48, 5, 10, 20, 40, 7, 14, 28, 56, 11, 22... It may have then gone back and "scooped up" each nontaken number before moving on to tracks 65-128, doing the same thing.

I'll take Rockboxes "pseudo" random any day.

[ryran]

hahaha.. that's hilarious.
(er, hideous.)

[snakebite]

Hmm.  I've actually been thinking of dumping Rockbox because the shuffle is not random enough.  I listen to my player every day at work for hours.  I doesn't take long before you start asking why you keep hearing the same damn songs every day, and wondering why you never, or rarely,  hear some others.  When I had my archos jukebox with Rockbox, this lack of randomness drove me up the wall.  Now that I'm running a Sansa Fuze, it seems better but still flawed.  It over-weights artists that have more tracks.  You'd expect these artists to be played more, but not to the degree that I'm hearing.  I might have 20 tracks by Stevie Ray Vaughan in my library of 2000 tracks.  I know when I fire up the Fuze, I will hear Stevie several times in the first half hour.  And it hits up other artists that have more tracks in the same fashion, so that you start hearing these artists again and again and again.  Maybe I'm wrong, but I thought the Sansa shuffle seemed more random without Rockbox.

[Llorean]

If you have a library of 2000 tracks with 20 by Stevie Ray Vaughan, 1 in 100 songs will by Stevie Ray Vaughan if you listen to the whole library.

If you reshuffle each time, luck could present you with all of his songs, in order, as the first things you hear every single time. Or you could never hear them. That's why it's called "random."

There is no weighting. Each song appears once in the playlist. So obviously if you have more of a given artist, you're more likely to hear it. I'd wager that, assuming no bugs, you're just noticing Stevie Ray Vaughan coming up often because you felt it came up surprisingly often the first time, and now you're noticing it each time.

Try marking down every single song played (just the number of songs) and the number of Stevie Ray Vaughan songs over a few weeks, and see if the ratio really isn't proportional to the ratio between the total number and the number of his. If after a few weeks he really is showing up disproportionately often, it suggests a bug and is worth investigating. If it doesn't, then it's just you expecting to hear it more often and so noticing it more often.

[soap]

Unless there has been a regression somehow in the last two years this is observation bias.

If there were one, the test is easy:

I tested it by creating 10 thirty one second mp3s, and tagging them with track titles 1->10.

I then "insert shuffle" the containing folder over and over and over and over and over and over.

I then saved said dynamic playlist, and plotted the first 50% of it.

The distribution was random.

EDIT:
They were 31 seconds long because they were also my Last.FM test files.  There is no need to make them this long.