Super Random Number Picker

21:14.45 - Monday 24th October 2005   (Link to This Entry)

Over the last few days I've managed to get myself back into the mindframe where I can think about the new Lottery site that I'm working on, and actually do some more with it. Having not touched it for a few weeks I was a little bit rusty, but the improvements in coding practices I've been putting into use have paid dividends and it's actually been quite easy to get back into the swing of things.

Yesterday I put some finishing touches to the mailing list section, where members can add email addresses to their account and have the results sent to other people in their syndicate. It's not a big deal, but it needed doing. Tonight's problem was how to implement and more-random-than-usual number generator.

With traditional RNGs there is always the chance of one or more numbers getting more than their fair share of hits while others get none. Imagine this applied to a permutation of lottery numbers and you can see why a ball not appearing anywhere can be a pain in the arse, especially if the same number actually shows up in the results.

So the basic requirement was to somehow spread the randomness to ensure that all available numbers got roughly the same number of hits. In an ideal world there would only be one hit difference between the most popular and least popular numbers while still being random, and that's what I've gone for.

I've achieved this by using the number of hits a ball receives as a weight. Balls are grouped by weight, but within that weight band they are ordered randomly using your common-or-garden variety random number generator. On the first run, all of the weights are zero and we pick the lowest six in the array. We then increment their hit value which puts them near the top of the array. Next up we randomise the numbers again but keep them in their hit-weighted bands, so that the ones all stay near the top. Picking the lowest six numbers gets another set of six zeroes which we increment as before.

The point at which it gets interesting is when we don't have six zeroes remaining. Imagine that we only have four, and all the rest have been incremented to one. We randomise the hit values within their bands again and pick the bottom six - four of which will be our last zeroes, and two of which are ones, picked at random. After incrementing them all we have two balls with two hits, and the rest with one, and the whole thing continues in this fashion until we have as many random picks as the user specified. Hit values are never more than one apart, and everyone's happy.

It's an imperfect solution because it's still possible to get repeat picks, but it eliminates the problem of having one ball turn up too much and another not at all and that's the whole point of the excercise.

My Folding@Home Stats

21:59.47 - Monday 24th October 2005   (Link to This Entry)

A short while ago I jumped on the Folding@Home bandwagon, offering up my twin-core CPU to the gods of SAGoons (Team 150!).

Interestingly, I don't go above 50°C even with both cores running flat out. Nice!
(Hah! I just checked and I'm at 51°C - that'll teach me!)