We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. - Donald Knuth
You're bound to be unhappy if you optimize everything. - Donald Knuth
Rules of Optimization: Rule 1: Don't do it. Rule 2 (for experts only): Don't do it yet. - M.A. Jackson

After these careful recommendations, we can begin with this subject.

I was charged, by a friend, to develop a simulator for a mass multi player on line strategy game, in order to know the possible results of a fight between two fleet of spaceships. It sounds easy work, yes, for each ship (with it's own damage, life and shield attributes) of a fleet, simulator take *randomly* one ship from the enemy's fleet, and fire, if the damage of the attacker is less than 1% of the shield, then he can't touch, but if he can, and the enemy's ship has less than 70% of it's life it may *randomly* explodes. After that, if the attacker has a certain type of shoot against the defender (call it, rapid fire), it has a probability to get a new target, so it *randomly* can re-shoot.

Believe it or not, when I saw this problem, the first thing I tried to design, was an algorithm to reduce the problem of memory consumption, because each fight may involve hundred of thousands ships, and each ship has two specific value, shield and life, so a common implementation should be, for each type of ship, an array of N cells that represent a ship at a level of destruction (for shield / life). That is premature optimization... Of course, I developed during a few weeks a model that, once tested, was completely broken and deadly slow, for a bad reason : avoiding the growing usage of memory for growing fleet. The point was a CPU problem, and I thought about memory first, what a bad idea ! Thus, I recode it as an array of ships (one cell per ship, but I reduced the size of the ship structure to deal with the memory storage usage), that was faster, but the overall algorithm was still slow.

I finally decided to profile the application, it was a working application, just slow, but I had my unit tests developed, thus I was not taking huge risk to try the optimization... That was good optimization time, no more premature.

I never thought that it was possible to optimize the random function... I mean, I knew there was huge difference between a cryptographically secure pseudo-random-number-generator algorithm and a basic PRNG algorithm, but didn't know that an under-basic PRNG algorithm function actually exists.

For the moment, (a few months of use and abuse of this simulation program), I did not suffer from cycling values or false random, so I provide you the code I found on the outstanding web site of Bob Jenkins (It is basicaly an algorithm from knuth that I read on Bob's web site burbleturtle).

''Random Number Generators (for simulation)

Pseudo random number generators mix up a state like hash functions, but they don't take any input. They have a state of their own, and they just keep churning it. They produce random-looking sequences, which can be used as fake data.

The standard reference for this is Knuth's "The Art of Computer Programming", volume 2 "Semi numerical Algorithms", chapter 3. He recommends the random number generator

  for (i=0; i<55; ++i) rsl[i] = rsl[i] + rsl[(i+24) % 55];

although not quite as succinctly as that. It's really quite good, and it's hard to beat it for speed. Properly optimized, it takes about 8 instructions to produce each 32 bit word. The whole 32 bit word can be used, although the low-order bit is less random than the other 31 bits. Any set of 55 consecutive results has no statistically significant patterns, because every such set of results is possible.

If you have an application that is sensitive to obscure biases (like every result being the sum of the results 31 and 55 before it) then a better generator to use is ISAAC, which takes 19 instructions to produce each 32 bit word, and has no known biases.

Here are some tests for detecting bias in sequences that are supposed to be random.''

The application using this optimization can be found here.