need assistance with random number generator

How would I go about creating a very simplistic random number generator, with values in the register in the range from 01-04?

Thank you.

One of the simplest PRNGs to implement is a linear feedback shift register.

http://en.wikipedia.org/wiki/Linear_feedback_shift_register
Essentially the operation is a shift with a conditional XOR. You can implement it as narrow or wide as you like, so you might want an 8 or 16 bit version.

You get approximately 1 bit of entropy per iteration, so for a random number from 0-3 call it twice before using the result.

If you just want a quick random number and it's acceptable to have "poor" entropy, you can just call it once and use the result.

Here's an example 8-bit LFSR. The variable _prng_seed can be given any initial value except 0. 0 creates a dead cycle to itself. (Also note that it will never give you a value of 0 for the same reason, but this is not normally a problem since you will likely be masking the result to a smaller range.)


Edit: modified due to a problem pointed out by Bogax.

Many thanks!

um, it's got two cycles, 55 and everything else (it sticks on 55 instead of 0)

I was under the impression that unmodified LFSRs necessarily had a dead (self-recurring) point...

There's a dead point, all right, but you can hit it only if you start out in it.

Take the case of the LFSR used to generate noise in the NES APU. You never happen to start in such a state for the long sequence. It is possible to switch to the short sequence at just the right time that it ends up stuck, but briefly switching to the long sequence for a few periods and then switching back will always unstick the short sequence.

Ack! Thanks Bogax!

Sorry about the confusion. It'd been a while since I wrote the code and for some reason I mistakenly remembered it as having a 256-length sequence instead of 255. I don't know why I thought that, I dug up my test logs from the time and they clearly state it has a sequence length of 255, so I know I was aware of it when I wrote it.

I've simplified the example so that the dead spot is at 0, rather than 55. (The XOR with $59 was merely an aesthetic thing to break up certain sequences.)

You linked to the Wikipedia article, but what you've implemented isn't an LFSR by any definition I've ever seen - where exactly did you get it from?

An 8-bit LFSR requires XORing four different bits in order to get maximal length, while a number of other lengths (including 7, 15, 23, and 31) only require 2 bits.

Here's code for an actual 31-bit LFSR - it's not particularly fast, but the output is fairly good. As any LFSR, it generates randomness one bit at a time, and this particular one allows passing a number of bits to generate (1-8):



Shrinking this one down to 15 bits is fairly straightforward, and there's probably plenty of room for optimization as well.

It's identical in operation to the Galois LFSR described in the wikipedia article. What is your definition of LFSR?


The XOR mask $4D has 4 bits set. If an alternative is desired, all of the following produce a 255-length sequence for the code I pasted: $1D, $2B, $2D, $4D, $5F, $63, $65, $69, $71, $87, $8D, $A9, $C3, $CF, $E7, $F5

Ah, I must've misunderstood that section - the only LFSRs I've ever used are Fibonacci ones. Never mind.

The difference between the two is analogous to the difference between multiplication by 2 and division by 2 in a finite field. Galois LFSRs run "forward" and Fibonacci LFSRs "backward" (or vice versa if you learned it the other way).

And it's possible to optimize a 16-bit LFSR to generate 8 bits per iteration. Look up Greg Cook's CRC-16: 8 bits in 66 cycles without a huge LUT.

I rather like the Batari BASIC rand16
which justs shifts the two bytes of a
16 bit LFSR in opposite directions then
EORs them together.

That's a pretty neat one, bogax.