[malko]

Funny to note that today from another thread I red something similar on uridiumauthor.blogspot.com
(you will have to turn off the Firefox tracking protection to see the blog ) :

Random Numbers
I`ve seen people ask questions such as: "how do I get a random number between 1 and 3 quickly?" The fact is that most random number generators are algorithm-based, so no random numbers are delivered all that quickly. In fact, the only time I`ve found a hardware way of getting a random number was on the C64 SID chip. You could set the third channel to noise waveform, rack up the frequency, and read out out the current waveform value. I used to direct all the noise sound effects to that channel, and when it had finished I switched the sound channel to play silent high-frequency white noise. Any time you need a random number; just read it off the SID chip: 1 assembler instruction, nothing faster!

The advantage of algorithm-generated random numbers is that they can often be seeded, so you can get the same set of numbers out every time. In my latest game I could watch the first titles sequence, with supposedly random things happening, and every time the first demo sequence ran, it did exactly the same thing. To change that, I now get a timestamp of when the program starts, and seed the system random number generator with that. Now I get a different demo every time I start the program. I`m still not happy about the time that the system algorithm takes to supply a random number. Firstly, I have no idea actually what algorithm it is using, but secondly, that might change at any time if someone decides to alter the C library.

In order to supply my game with random numbers faster than the system can, I get an array of 256 numbers in advance from the system. I refresh that every time a game starts. Getting 256 numbers at the beginning of a game doesn`t take a great deal of time in the grand scheme of things, the player is just getting ready to play and likely you`re doing some kind of arrival sequence anyway. I then keep one index pointer into the array of random numbers and my fast call pulls out the next entry and shifts the index along by one. It just has to make sure it doesn`t fall off the end of the table. Actually an assembler optimisation for that would be to start at the end of the table so you decrement the index and easily detect the underflow case that resets the index to the end. It saves a compare. In C, the get a random number function is so short that on a RELEASE build it`ll likely drop in the code in the function rather than calling it.

Coming back to the random number between 1 and 3 then... I would always try to avoid anything that doesn`t involves powers of 2. Scaling our 32-bit random number to a lower power of 2 is again just a case of logically ANDing the random number with a mask to reduce the scale. ANDing with 0x03 gives you an equal chance of 0, 1, 2 or 3. None of the powers of 2 are divisible by 3, strangely enough. If you do want to do that then you could do it quicker by, say, getting number between 0 and 255, and testing it for being less than 86 for 1 route, less than 172 for the second, else the third. The only faster way is to set up a specific array of random numbers between 0 and 2 for later diving into.

The process of setting up an array with answers to complex calculations in advance is nothing new. On the C64 the screen was 40 characters wide, and there was no multiply instruction, so a little table of 25 entries with multiples of 40 in it was great for calculating the screen character address at a particular co-ordinate. You would divide the Y pixel co-ordinate by 8 by using the logical-shift right instruction 3 times, then look up the multiple of 40 in your table, then take the X pixel co-ordinate and divide by 8, and add that on.