Rolling The Dice, in A Pseudo-Way
Some Random Words on A Pseudo Topic
Introduction
This topic goes against every other thing you have ever been taught about programming. In most/all other areas you need to design and program solutions which are predictable, logical and reliable. In short, there should be no surprises and no random elements. Everyone knows that computers are dumb, robotic things which follow the same, identical sequence of instructions over and over and over again...
But in this subject we want random, or something close to random, numbers to be created. In short we want a seemingly unpredictable sequence of numbers from which a pattern is impossible, or difficult to make out.
You may have heard that computers and electronics can not generate truly random numbers. In fact (in my very humble, stupid opinion) there is no such thing as "random-ness" or "chaos", I know this goes against all the modern, trendy fractal zoom worshippers, but that smart cookie, Einstein and his joke about dice and God will perhaps be proven correct in the end.
So what's the basic argument about following the "Chaos God" way of thinking?
"There are these things in nature which appear to be random, we try to predict the outcome and we can't... It must be CHAOS!!"
But perhaps this is man's own ego. "We can't predict it.. must be chaotic!" I don't want to re-write all the laws of physics, burn books with Chaos thrown across the covers, but I just have this feeling that Mr. E is correct. Next time you seen/read a demonstration using three magnets with one on a string and the other two fixed just listen to the explanation...
"We know that there is nothing chaotic about the system, we know the laws which are affecting the magnets very, very well. But when we come to try and predict the outcome, we can't. It appears to behave in a random manner."
Simple Sequences
Computers are very good at counting (unless you have an old Pentium, heh heh). So it is a trival task to count up from 0 to some number by using a certain step value.
For example we can count all the multiples of 7 simply by adding 7 to a variable for each iteration.
n = n + 7
So this would give the following number sequence:
0, 7, 14, 21, 28, 35 ... etc ...
It's a very simple method, but it is far too predictable to be of any use.
A Shifty Algorithm
A common way to improve the previous number-stepping method is to rotate the number as well as adding an increment value to it.
n = n + 7
n = n << 1
Or in 80x86, something like this:
.data
n dw 0
.code
add [n], 7
shl [n], 1
The shift instruction helps to scramble the bits more than a simple add would do. Usually a rotate is used so that the top bit is fed back into bit 0.
Another common operation is the XOR instruction.
n = n XOR 7
n = n << 1
Or in 80x86:
xor [n], 7
shl [n], 1
Or using a rotate:
xor [n], 7
rol [n], 1
Of course you should choose an increment which gives a wide range of scattered values for [n], we don't want a really predictable sequence.
Cyclical Generators
Because we are using a small, finite number of bits to store the number in (16 bit in the previous examples), we will eventually end up with the starting number, i.e. 0000.
Another important part of most/all pseudo-random number generators is that after a number of iterations the same sequence of numbers will be generated again. Hopefully the number of iterations between each "cycle" (the number of call before the sequence repeats) will be reasonably large.
What we really want is a fast generator which has a very high cycle count.
Back to the past
A large number of years ago I looked at the old ZX Spectrum RND algorithm which was quite a simple piece of code. It has a really nice attribute, it generates every number between 0 and 65535 just ONCE. So it has a perfect spread of numbers. After the 65536th call the sequence begins again from the start.
The ZX Spectrum algorithm was this:
n = n + 1
n = n * 75
n = n MOD 65537
n = n - 1
And, no, that's is NOT a typo. It is 65537!! (00010001 hex)
And here is my solution in pure 8086 code:
.data
n dw 0
.code
mov ax, 75
mul [n]
add ax, 74
sbb ax, dx
adc ax, 0
mov [n], ax
As you can see (or not in this case), there is no MOD 65537 operation. It's been so long since I worked this out that I have forgot how I did it. As this only gives a period or "cycle" time of 65536 iterations it is interesting, but not really that good for a proper generator.
FSR (Feedback Shift Register)
I can remember a friend (who knew a lot about electronic, hey, he even designed and built his own computer, including the video chip!!) telling me about this technique in a very simple form.
The idea is very similar to the shift/rotate method. You scroll the bits in the rnd number and perform a scramble step to calculate the new bit to be shifted in.
One simple algorithm would be to rotate and XOR the result if we get a carry.
rol [n], 1
jnc skip
xor [n], 1
skip:
You could of course extend this to 32 bit and perhaps use the BSWAP instruction to help scramble the bits even more, to hopefully give a more random looking sequence of numbers.
One nice FSR pseudo-random generator I found recently was the "Whiz Kid Technomagic Random Number Generator" at http://www.bigfoot.com/~whizkid.
The really interesting thing about that algorithm that it reports to give a cycle period of... wait for it... 549,755,813,887 which should be enough for most people.
Iffy Programming
There are plenty of example of dodgy generator, including using the executate code as a list of rnd numbers, reading from the video chip, reading from the timer countdown registers, or using the DMA refresh registers.
Most of this techniques are okay for initialising the random number seed, but can be slow, not to mention down right dangerous to your machine.
For games it is often nice to be able to generate the exact same sequence of random numbers again and again by re-initialising the same seed start value. This is good news for demos in which a game has been played and the player's actions have been recorded. If the enemies (monsters etc.) use some random elements in their decisions then it is VITAL that the same random number sequence occurs, otherwise the monsters may walk left instead of right and so it looks like the player is reacting to nothing. Or even worse, the monster kills the player even though it didn't when recording the demo.
Or perhaps the map/world creation is based upon a random sequence. If the player dies and wants to restart/continue on the same level then it is vital that the level is created in exactly the same way.
As you can see, sometimes have a predictable sequence is nice, but having a predicate sequence with a very long cycle period is even nicer.
Closing Words
I haven't really had time to look at the "Whiz Kid Technomagic Random Number Generator" in any detail, but it sure looks very promising and I suggest that everyone takes a quick look at it. Respect to G. Adam Stanislav, nice job, but I think the code could be made shorter and perhaps faster.
As G. Adam Stanislav said, the algorithm is so easy (after all it is from an electronics book!!) it is surprising that Intel haven't created an instruction to do this same.
Or perhaps they did, in the form of the old Pentium DIV bug.. heh heh.
Random Regards