8-bit random number generator

[chitselb]

This is on page 172 of Butterfield's "First Book of KIM-1"

Code: Select all

            xxxx D8      RAND CLD clear  decimal if needed
            xxxx 38           SEC carry  adds value 1
            xxxx A5 13        LDA RND+l  last value (E)
            xxxx 65 16        ADC RND+4  add B (+ carry)
            xxxx 65 17        ADC RND+5  add C
            xxxx 85 12        STA RND    new number
            xxxx A2 04        LDX #4     move 5 numbers
            xxxx B5 12   RPL  LDA RND,X
            xxxx 95 13        STA RND+l,X  ..move over 1
            xxxx CA           DEX
            xxxx 10 F9        BPL RPL    all moved?

I use it as my random number generator, but what better (other) options are there, for, say, 8-bit and 16-bit random integers?

[hoglet]

Here's the one used by Acorn Atom Basic:

Code: Select all

C986  A0 20     LDY #$20
C988  A5 0A     LDA $0A
C98A  4A        LSR A
C98B  4A        LSR A
C98C  4A        LSR A
C98D  45 0C     EOR $0C
C98F  6A        ROR A
C990  26 08     ROL $08
C992  26 09     ROL $09
C994  26 0A     ROL $0A
C996  26 0B     ROL $0B
C998  26 0C     ROL $0C
C99A  88        DEY
C99B  D0 EB     BNE $C988

It's implements a 33-bit linear feedback shift register (taps at bits 20 and 33) that is clocked 32 times.

Dave

[Chromatix]

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.

[GARTHWILSON]

If you have a VIA whose T1 (timer 1) you can set to free-run, reading and using the T1 value in part of your algorithm adds randomness since the times you read it will be rather random.  If you're using T1 for a software RTC (real-time clock) running on interrupts, there is the slight problem that reading it just as it's about to generate an interrupt will clear the interrupt condition and make your RTC miss that tick.  The chance is about .002% in my case where I have 100 ticks per second on a 5MHz computer.  If that risk is too high, you might want to use a second VIA's T1.

[Chromatix]

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.

[floobydust]

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.

[Chromatix]

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.

[GARTHWILSON]

Using the timer itself as the source of the random number was not the intent.  Instead, do something like read its 16-bit value and do some scrambling by multiplying by $7ABD (which will cause overflow and we don't care about losing those high bits, since we're after random numbers anyway) and adding $1B0F (which may cause addition overflow, and again, we don't care).  The result will be MOD(T1*$7ABD+$1B0F, $10000).  You can of course go further with the scrambling and with saving one or both bytes or portions of past outputs to involve in the formation of future ones.  This is for 16 bits.  If the OP wants only 8 bits, the same idea can be carried out with half the precision.

[Chromatix]

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.

[GARTHWILSON]

Keep in mind that even the multiply takes differing numbers of cycles based on the inputs, so the timer count becomes more random.  It definitely won't be multiples of some number, even if you do a loop to generate an array of random numbers.  T1's low bits will be all over the place.  You also don't know what T1's starting value will be.  Shuffling bits, XOR'ing, rotates, etc. are definitely allowed as well.

[commodorejohn]

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.

[Chromatix]

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.

[cbmeeks]

Chromatix wrote:

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.

[White Flame]

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?

[Chromatix]

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.