Improving on System.Random for gaming and simulation
The algorithm for grabbing samples in the System.Random class comes from Numeric Recipes in C, Second Edition. They've made some small changes to how the algorithm is run, to either improve performance, or improve the random characteristics of the resulting data. However, they did change some key lines, or what might be considered key lines (according to Knuth).
Currently, I have a couple of problems with the random number generator. It is virtual, so there is some call overhead. They are using a possibly unproven method (not really, but there isn't as much testing on this method as some others). It is pretty fast, I do have to give them that. Knuth's method is one of the fastest RNG's that actually produces decent random results over a large period. Here are the items I want to improve on over the next week:
- Additional options: I'd love to provide 5-10 different random number generators of varying speeds, randomness, and period repeats. I'll be writing each method in C#, along with any statistical data detailing how strong the algorithm is and how fast it is. I'll try to include pitfalls for using the algorithm or invalid seeding notes, but only if I find reference to them on the Internet (hint: this is not a full examination of random numbers, but instead an attempt to provide randon number options for people making games or doing simulations).
- Theory of Randomness: I'd love to provide some good history on the theory of randomness. Just having an algorithm often isn't enough if you don't know why you need to go to such lengths in order to get random numbers. In most cases linear congruential generators would appear very appealing to the majority of users, because looking at the randomly generated numbers it would seem okay. It is only after you look at millions of them, that you realize the faults in the system.
- Testing for Randomness: Personally, I've never really found any good testing models for randomness. I've used some statistical modelling for bit runs, bit group runs, total bits, etc... All of the basic stuff. But there are so many hard core and off-the-wall tests out there that I thought it might be cool to examine some of them. This step will really have to be examined first, since the test suites found and the test suites created will be used to examine each of the random number generators.
- Game Generator Considerations: Recently there have been concerns that true random number generators are too random for game players to trust. In true random generators players get the feeling that the generator is broken if they get a string of bad luck. This is exacerbated by the methods most generators use for creating random numbers within small ranges that are much smaller than the underlying random sample. So while in some cases the generators appear broken, in others they actually are broken, and believe me, players see this. We'll discover enhancements that can help weed out strings of *improbable* numbers that the user might confuse for a broken random number generator.
References:
Numeric Recipes in C, 2nd Edition - This book definitely has loads of random number generators, but they don't talk about why the random number generators are any good. They do, however, cover random number generators with uniform devitates (we'll be focused on these), and also many without focused on the Monte Carlo method, Poisson distributions, and Gaussians.
AI Game Programming Wisdom 2 - This book has some great insights on not-so-random random number generation to confuse the player ;-) I say confuse, but it is really to appease the player and give them the feeling the world is in order.
Intel Random Number Generation - A good article on the intel random number generator and the tests they've undergone to make sure everything is up to speed. I've also heard of a random number generator being created by intel that resides on the chip and uses thermal variances (why by call accounts should be truly random) to compute an actual random number.
Florida State, DIEHARD - Florida State has created a series of tests known as DIEHARD. These have been used by the intel group in the brief, so I figured I'd either implement their testing suites in the managed world, or at least use them for sanity checks.