6502.org

This is on page 172 of Butterfield's "First Book of KIM-1"I use it as my random number generator, but what better (other) options are there, for, say, 8-bit and 16-bit random integers?

Here's the one used by Acorn Atom Basic: It's implements a 33-bit linear feedback shift register (taps at bits 20 and 33) that is clocked 32 times.

Dave

PRNGs are a rich and varied field. It's easy to generate low-quality random numbers, much harder to generate high-quality ones, and harder still to do so quickly and in little RAM. A common failing, for example, is to make the low-order bits of the output repeat in a short cycle - making the common pattern of "dieroll% = (RND() MOD 6) + 1" useless.

The Mersenne Twister is well-regarded for use on modern computers, but is probably too heavyweight for an 8-bit micro (unless generating random numbers is its primary function). Another good option, though a slow one, is to use a cryptographic hash function (eg. SHA-256) repeatedly; I actually did this for my winning TDWTF contest entries a couple of years ago, though in a way that leaked part of the state (it was an underhanded-coding contest).

One promising approach, if you can dedicate an entire page (256+6 bytes) of RAM to it, is the Spritz cryptosystem, which can be used as a PRNG. It works in a very similar way to RC4, but is probably more robust. What's more, if you have a source of truly random data (eg. from timing human inputs or from a thermal noise sampler), you can inject it into Spritz to make it non-deterministic.

That approach only works if you aren't reading it in a programmed loop - if you are, then the values returned will be highly correlated. Reading it in response to human input is okay, because that has a lot of entropy.

Another thought... using a UART like one of the NXPs might work out better, as it has it's own 16-bit counter/timer. As it (can) run on a separate clock from the CPU, reading the current counter registers would produce a more random result with a programmed loop as the CPU clock is separate (and assumed to not be the same frequency).

Granted, it's just an idea... I've not gone back to visit the datasheet to see if a read of the counter registers would disturb the overall timer/counter function. I use it for a jiffy clock (10ms) on my latest SBC.... might just take a look at that and see if it's doable.

Using a timer counter as a jiffy clock is perfectly fine - it's what they're designed for. Using one as a source of randomness is not - even if it runs at a different rate to the CPU clock, it's still a *predictable* and *constant* rate with almost no entropy (a theoretical measure of randomness). This would make your RNG useless for straightforward Monte-Carlo analysis, such as rolling some dice or shuffling some cards many times and working out the distribution of results. In fact, the behaviour of the RNG in such a workload would be similar to that of a very poor linear-congruential PRNG, cycling its low-order bits in a short, repeating sequence.

Using a simple LFSR, as described at the beginning of this thread, is a better alternative to that. You could initialise the LFSR on boot with the reading from a persistent RTC chip, if you wanted to avoid repeating sequences every boot.

Someone asked me privately how to use Spritz as the core of an RNG. I think it's best to link to Bruce Schneier's introductory summary of the cryptosystem: https://www.schneier.com/blog/archives/ ... ew_rc.html and the original authors' paper: http://people.csail.mit.edu/rivest/pubs/RS14.pdf

As Schneier notes, Spritz is a "sponge function" which can absorb data and then squeeze out a stream of pseudo-random bytes. In the simplest PRNG application, you would "absorb" a seed value - possibly a constant, such as the contents of your boot ROM - and then whenever you need a random value, you just "squeeze" out however many bytes you need to construct your output. The paper explains how to do that in ways which safely distinguish it from its alternative uses in cryptography. If you have a source of true randomness, you simply "absorb" the output from your random source whenever it's available.

One way to build a true random source, which doesn't rely on having human inputs to time, is to AC-couple a suitably biased diode to a comparator, which in turn feeds into a shift register. Occasionally reading and absorbing that shift register's contents should produce enough entropy to keep Spritz output unpredictable. Note that while random, the output of a noise source is not necessarily unbiased; Spritz effectively acts as a "whitening filter" which removes the bias.

As given, that formula does not improve the statistical quality of the numbers obtained. In particular, the least significant 2 bits are unchanged by the multiply, and the addition has no statistical effect whatsoever.

XORing the high word of the multiplication result with the low word might be an improvement, as would XORing in the previous value returned, but I would still be skeptical.

Of course, the real question here is "how random do you need it?" Chromatix is probably right in his overall analysis, but whether it makes a meaningful difference depends a great deal on whether you're trying to do military-grade cryptography or just writing a blackjack program.

Arguably, a blackjack program demands a relatively high-quality RNG! But having the timing of card deals depend on human input should introduce enough entropy to make the deals fair.

I think it depends on the human.

I've met people in my life that I are so robotic in nature that any curve ball thrown at them causes them confusion.

For example, many years ago I supported a small company with their IT needs. One user was in his 60's at the time and never like those "confounded computer machines". Anyway, there was this program he had to use every day and the icon for it was on his desktop. In the upper right corner. Well, somehow, the icon got moved to the left side.

He flips his lid! He calls tech support (me) and I go over there and he's telling me the machine is broken. He couldn't comprehend that the icon was not in the EXACT same spot. Now, he wasn't a stupid man by any means. It's just that computers were such a foreign concept to him that he literally developed muscle memory to:

1) Move mouse to upper right
2) Click twice (fast) on picture
3) Type <whatever> in first box
4) Etc..

Now, I get what you're saying about entropy in humans. But in all seriousness, that man could have easily been replaced with a simple script. At least for his computer work.

Here are mine for 8-bit & 16-bit generators. They're tested to go through all 256 or 65535 numbers uniquely before repeating (and different EOR values order those chains differently), so they're good for doing certain utility or game things, like a fade-out dither.

By the way, what's "better"? Stronger randomness, smaller time/memory footprint, or some other property like the above?

There are two properties that people look for in an RNG's output: statistically uniform, and difficult to predict given previous output. The latter inherently implies that the internal state is larger than the output, which unfortunately is not true of your small LFSR scramblers. It *can* be true of a larger LFSR, of which only part is used for output.

Such small scramblers can be useful in limited contexts, where iterating chaotically through a given set of values precisely once is, in fact, what is desired. But they don't meet my definition of a good PRNG.

Speed and memory usage are also important characteristics. As I noted, there is often a tradeoff between these and the quality of the output.