Using Random Numbers

Why?

When using a microcontroller to automate a haunt, it is useful to have a source of random numbers. Here's why...

Surprise is a strong component of any scare. Some scares rely purely on surprise, and without surprise, there is no scare. But even if the scare does not rely on surprise, adding an element of surprise enhances it.

If a kid walks past a scene and a monster always pops out, it is predictable. It is especially bad if each kid in line triggers the monster - "goodby Mr. Surprise!" because each kid sees the monster popping out for the kid in front of him. Even worse is an automated scare triggered by a dumb person sensor, like a pressure mat. You will soon have one kid stomping on the mat to pop up the monster, and telling his friend, "Hey, look! When I stomp here, the monster pops out!"

This situation can be improved by adding a timer to the trigger system. If the kid walks past the spot and the monster only pops out if it has been 10 seconds since the last pop, it is better, because each kid doesn't see the previous event.

But what if your monster flipped a coin for every kid passing by, and only popped out after the coin came up two heads in a row? The monster's appearance is unpredictable, so surprise goes up, and so does terror.

Basics

Let us assume that you are using a BASIC Stamp or PROP-1 to control this scare. You want there to be an input that says "kid is present; OK to scare". The controller would have an output that it can turn on to trigger the monster pop-out. And you would write a little program to tie the sensor to the output. By making the controller wait a little while, you can get the previous kids out of the way before even considering the next scare. Fine!

But how can the controller "flip a coin" to determine whether or not this kid gets it? The BASIC Stamp and Prop-1 controllers contain a RANDOM function that provides pseudo-random numbers.

What Do You Mean By Pseudo-Random?

Why pseudo-random? It turns out that true randomness is often difficult to get. But we can often get by with fake random numbers. Let's take an example...

Consider this sequence of digits:

26535897932384626433832795028841971693993751058209

Do you see a pattern in there? I don't. It looks pretty much random. But if I told you that the previous digits were 3.14159, you might recognize the sequence as digits of the constant pi. Pi is a very well-known number; most school children know at least the first few digits of it. There are some people who have memorized hundreds of digits of pi. But when used in an unexpected context, the well-known sequence seems to be random.

Althought I just used Pi as an example, it isn't terribly useful here, because calculating the digits of pi requires a lot of effort. But there are some simple mathematical operations that produce long sequences of numbers that appear to be random - if you don't know where they are coming from.

There are many types of mathematical operations that can produce these pseudo-random numbers (PRNs). The folks at Parallax picked one such PRN generator (a "PRNG") and put it in their controllers, for our use.

The RANDOM Statement

You get the PRN by executing a statement like this:

RANDOM   MyNumber

This is an interesting statement, because the variable MyNumber serves as both input and output. Before you execute this statement, MyNumber contains a value known as the "seed". The RANDOM function bashes up this initial value in a predetermined way and puts the result back in MyNumber for you to use. MyNumber (in and out) is a 16-bit value.

BEWARE: Every time you give RANDOM the same input value N, it will return the same output value M. Remember: this isn't really random. But if you only set up the seed value once, each time you call RANDOM it will chase its own tail (taking as its input that which it produced last time).

RANDOM is documented as generating a sequence of 65535 pseudo-random numbers, so you can call it many times, getting a new value each time.

That's about where the instruction manual leaves you.

How Do You Use PRNs?

How do you use these pseudo-random numbers?

Let's say we want the monster to pop out 50% of the time (1 of 2 calls to RANDOM; half the time). Since RANDOM can return any one of 65535 PRNs, you could take 65535 as 100%. Then half of that would be roughly 32767. All you need to do it call RANDOM, and if the result less than 32767, fire the scare.

Let's say that you want the monster to pop only 25% of the time (1 of 4 calls to RANDOM; a quarter of the time).

65535 / 4 = 16383

Now you just call RANDOM and if the result is less than 16383, pop the monster.

Whatever percentage of the time you want to pop the scare can be used to calculate a portion of the 65535 PRNs, and give you a number to test for. You could even make .1% of the kids win a real gold coin.

But it gets better! Why just have two choices? You could easily write a program to:

pop a monster on the left 25% of the time
pop a monster on the right 25% of the time
flash a strobe for 10 seconds 25% of the time
give out a gold coin .1% of the time
and do nothing to the rest of the kids!

Lies The Manual Told Me

The RANDOM function is documented as giving a new 16-bit number each time. If that were true, it would be a waste to generate all of those nice random bits, just for a couple of percentages. I leave it as an exercise for the reader to simplify the math and take better advantage of RANDOM's output.

Unfortunately, the Stamp manual lies when describing the output of RANDOM. I have done some experiments with the function and found out the following:

I confirmed my earlier suspicions that the particular type of PRN generator used is a linear feedback shift register.
RANDOM contains special-case code so that it does not stall when given a seed of 0.
The register is shifted once to the left for each call.

Thus each call to RANDOM does not return 16 fresh random bits. Each call returns a single new random bit, and 15 previously-seen values, moved one slot to the left!

Here is some sample output from RANDOM:

RNDNUM = %0000000000000010
RNDNUM = %0000000000000101
RNDNUM = %0000000000001011
RNDNUM = %0000000000010111
RNDNUM = %0000000000101111
RNDNUM = %0000000001011110
RNDNUM = %0000000010111101
RNDNUM = %0000000101111010
RNDNUM = %0000001011110100
RNDNUM = %0000010111101000
RNDNUM = %0000101111010000
RNDNUM = %0001011110100001
RNDNUM = %0010111101000010
RNDNUM = %0101111010000101
RNDNUM = %1011110100001011

Notice the way that the pattern takes one step to the left each time?

This means that there is a relationship between the bits of adjacent calls that may become obvious, depending on how you use the PRNs. Example: If you use this function to flicker numerous LED "candles" they may have a "ripple" effect, where LEDs flicker in sequence.

Issues

There are several problem that mathematical operations to produce pseudo-random numbers may encounter. Whether or not the problem will appear and how severe it is depend on exactly which PRN generator is being used and how it is used.

Issues:

All PRNGs will eventually hit the end of their sequence and start repeating the sequence again. But if the sequence is long enough, you won't notice.
Some otherwise good PRNGs can get stuck in short sequences if not used properly.
Some PRNGs are slow.
Some generators produce PRNs that aren't very random. If your application requiresa high degree of randomness, you must be very careful in selecting and using a PRNG.
All randomness, pseudo or real, may emit small sequences that appear nonrandom. For example, a card player may just be lucky enough to get four kings, even if the deck is well shuffled. It's the luck of the draw. Likewise, a PRNG may occasionally emit a stream of identical digits. This doesn't necessarily mean that the PRNG is broken. It could just be the luck of the draw.

And always remember the words of mathematician and computer pioneer John von Neumann: "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."