Randomness in a script

Okay, basically I've made a TV object onto which you can drop images, and it will randomly select a new image every 30 seconds or so.
What I'm concerned with is that the randomness doesn't see to be very good, some images get displayed far more than others.

So, I'm running a test at the moment, basically leaving two TVs and letting them log stats on two different random methods:

Method the first:

integer count; list items; list stats;
integer i; // This is just a counter variable

default {
    state_entry() {
        items = ["a","b","c","d","e"]; // Here's our test list
        count = llGetListLength(items); // Count the number of elements
        for (i = 0; i < count; ++i) { stats += [0]; } // Populate the stats list with zeros
        llSetTimerEvent(10); // Start the timer
    }
    touch_start(integer x) {
        if (llDetectedkey(0) == llGetOwner()) {
            for (i = 0; i < count; ++i) { // Loop through all the items
                llOwnerSay(llList2String(items,i)+" - "+llList2String(stats,i)); // Output this item
            }
        }
    }
    timer() {
        integer x; // An extra integer
        i = llRound(llFrand(count - 1)); // Pick a new list item
        x = llList2Integer(stats,i); ++x; // Fetch the count for this item and increment it
        stats = llListReplaceList(stats,[x],i.i);
    }
}

Okay, so that's the whole thing using the first method (a simple llRound(llFrand(count - 1));) and the code for testing it with. Every ten seconds it picks a new letter and increments its counter. When touched by the owner it will output the stats it has accumulated.

The second method is to do this (timer event only):

    timer() {
        integer x; // An extra integer
        i = llRound(llFrand(llPow(count,3))) % count; // Pick a new list item
        x = llList2Integer(stats,i); ++x; // Fetch the count for this item and increment it
        stats = llListReplaceList(stats,[x],i.i);
    }

You'll note that this method takes the count of items and cubes it (the cubing can be adjusted if you fear racking up massive numbers with big lists) and it uses this to pick a random number. It then rounds it and uses the modulo operator (remainder when divided by) to return a number between zero and (count - 1). Perfect for a list of items.
Now in my shortened test (which I rushed last night) this second method actually achieved a more even distribution than the first method.
I'll report the numbers from the extended test (been running overnight at 30 second intervals) when I get home and log-in to check.

But I'm interested to see other people's thoughts on the randomness, and how they go about ensuring the number is truly random.

Note my TV script is much more complicated, it is also slightly different and is keeps generating random numbers until such a time as the new number no longer equals the currently display object (so the same image won't be displayed consecutively).

Well the first method would have problems with the ends. The first element (and I think the last element, sorry, early in the morning for me) will get hit half of the time of all the other entries. First list element has a range of 0 to 0.49, second element .5 to 1.49 (double the range of the first), etc.

Course I wouldn't be surprised if Frand is a rather lazy random function, kind of like some of the shuffle play CD players I've had in the past.

Need more coffee before I quite get your second method, but looks promising.

Oops, missed out the basic workings of it.

Basically it just takes a really big number (this could be a constant really big number, or the time of day squared plus a thousand or whatever you want, time of day being quite good as it changes all the time - horrible pun. Just so long as it's bigger than count. Actually I probably shouldn't have used llPow() as the example, since my test just uses 2 million odds.).
It then picks a random number from within this really big number, divides it by how many elements there are and gets the remainder. Since the remainder can't be the number of elements (as this would divide further) it is well suited for list operations as a 5 element list will return 0 to 4.

I guess the main concern is how likely it is to divide. For example if I have a number of a million, how likely is it that llFrand() will choose one that divides by 5 to give remainder 2?
Not an easy thing to go through mathematically (unless I missed it) so that's the reason for my test.

Many random number generators are not very good in certain ranges of bits, usually at the low end. The normal solution to this is to grab a different set of bits.

llFrand returns a float, so you're ALREADY working with the high bits and ignoring the low ones. If it still isn't working, you can change the distribution of bits used by your code like this:

integer random_number = llFloor(llFrand(desired_range * BIG SCALE_FACTOR)) % desired_range;

If that doesn't work, check for other possibilities. For a TV, llListRandomize is probably the best thing to use because it'll guarantee you'll have no dups except occasionally at the very end of a cycle:

list master_list = getmasterlist(however,you,get,it);
list cycle = [];

string next_picture()
{
    if(llGetListLength(cycle) == 0)
        cycle = llListRandomize(master_list, 1);
    string picture = llList2String(cycle, 0);
    cycle = llList2List(cycle, 1, -1);
    return picture;
}

My suggestion?

LIST that contains all the images, then make a copy of that list. While the copy of the list contains items, select a random image from the list, display it, remove it from the copy of the list, repeat until you no longer have any items in the copied list. Make a new copy and start over.

Don't try to get fancy with random algorithms as you'll never beat the Bell Curve.

[edit]

And of course reading the post above mine compleatly after I finish posting... that is exactly the type of solution I was describing, although I didn't use the Randomize list function.

Thanks for the responses! I'll give those a test too!
Speaking of which, the update managed to break my script meaning the stats were zero when I logged in, had to reset before they'd begin logging again =(

This is what I've gone for as my final solution:

if (count > 1) {
    if (!i) {
        llSleep(1 - llGetRegionTimeDilation()); // If heavy lag, sleep out of courtesy
        images = llListRandomize(images,1);
    } else { ++i; if (i >= count) i = 0; }
}
llSetTexture(llList2String(images,i),1);

images = list of image names
count = number of items in this list
i = counter variable to track where in the shuffled list we are

This is essentially the same as Agent Stonecutter's solution except that it randomised the list every time it reaches the end. Your original solution seemed to just reverse the list, which although retaining some variation isn't exactly THAT random. The benefit to efficiency seemed negligable as it's uncertain how much faster a list reversal would be compared to re-randomising it.

Thanks again to everyone who replied!

That's very strange, and sounds like a bug in llListRandomize unless there's some subtle logic flaw in my code I'm overlooking. Possibly llListRandomize does the same transform when it's applied to the same list every time? The obvious fix would be:

if(llGetListLength(cycle) == 0)
{
    master_list = llListRandomize(master_list);
    cycle = master_list;
}

No wait sorry, I think what's happening is that I'm just misunderstanding what you were doing with llList2List()! The whole menagerie of list functions confuse hell out of me!
I thought you were reversing the elements (which I believe is what llList2List(items,-1,0) would do?), but I see now you were actually removing the first element. Is it faster to do it that way than using llDeleteSubList()?

In that case all my solution does differently is that the list remains as it is before being replaced in a single step, rather then being replaced at every step. Possibly a slight improvement due to lists being quite nasty, as I only require an integer to keep track of where I am.
In this way mine is randomising the list, then randomising it again and again, opposed to reverting to the previous (untouched) list. Meaning I only need one list and one integer.

I'm interested now to see which will run most effectively actually, randomising an already randomised list, or randomising from the start list each time? I think I shall set-up a test tomorrow.

Since llDeleteSublist has to support merging two disjoint sublists, llList2List should be minimally faster... but its main advantage is that it's simpler and easier for my Lisp-infected brain to understand.

I assumed you had tried my version and found it behaving strangely, which is why I was surprised. I hadn't tested it, of course, because I don't have any computers fast enough for SL here... but I didn't think I was THAT far off!

I don't know if using an index over the list is faster or slower than creating a new list. It should be much faster to grab the first element off the list than iterate through the list to get to the indexed value, but if LSL is being really stupid with its list functions and is actually copying every element of the list each time your code would definitely win.

As far as randomizing the original list or re-randomizing the list goes, if llListRandomize works properly there should be no difference.

It was kind of implied by the comments above, but to make it clear. The right way to do this is to change:

i = llRound(llFrand(count - 1));

to:

i = llFloor(llFrand(count));

That should give you even odds.

I may be repeating someone. I didn't read the whole thread.
I've been thinking the current time would make a handy source of random noise. Time and date together and you get a value that won't be repeated.