8-bit random number generator

[chitselb]

White Flame wrote:

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.

So are these routines really 'shuffle' with a completely flat distribution?

White Flame wrote:

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

Great question! What are the ways of measuring randomness? I seem to recall 'Poisson Distribution' being a thing, but not having thought about that idea in 40 years, I don't remember the specifics or the applicability here. Wikipedia article suggested I'm on the right track. This is my list of measurable factors to determine "betterness"

• stronger randomness
• runs in linear time?
• fewer bytes
• fewer cycles

[Chromatix]

There is a thorough, if rather verbose, summary of PRNG criteria here: http://pracrand.sourceforge.net/RNG_engines.txt

[ppelleti]

Bob Jenkins has a 32-bit random number generator: http://burtleburtle.net/bob/rand/smallprng.html

It's perhaps more complicated than you'd want to run on a 6502, but it's still a lot simpler than Mersenne Twister. It has 16 bytes of state (organized as four 32-bit integers).

[dclxvi]

chitselb wrote:

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

Note that Butterfield's statement (on p. 172) that

Quote:

...it won't "lock up" so that the same number starts coming out over and over again...

is not correct. Initialize RND+1 to RND+5 to $FF and observe that RAND will return $FF ad infinitum.

That routine is a variant of a lagged Fibonacci generator, and lagged Fibonacci generators are notoriously tricky to initialize.

[BigEd]

I think PRNGs are rather like crypto: it's fun to roll your own, but not "safe" - there are too many pitfalls. And you certainly need to know what it is you care about: speed, size, safety.

I get the impression LFSRs date back to very early digital electronics, when shifting was not only easy, but natural, because machinery was often bit-serial. They remain a very good choice for 6502, because shifting is still cheap and natural. Anything based on multiplication comes from a later era, when machines could multiply cheaply - as we know, the 6502 doesn't have a multiply instruction.

I would go for LFSR myself, but as noted above, you need more bits in your shift register than you plan to pull out, and you need to spin it at least once per bit. It'll still be faster than naive multiplication.

And as also noted, initialisation is important - even more so if you care about the first few numbers produced.

[RichTW]

GARTHWILSON wrote:

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.

Yes, I used to do basically that. My 8 bit random number generator used to look more or less like this:

Code: Select all

    LDX randindex
    DEX
    BPL *+4
    LDX #12
    STX randindex
    LDA randtab,X
    EOR via_t1l
    STA randtab,X
    RTS
randtab:
    ; 13 random bytes

Fast and random, but not particularly rigorous.

[Dr Jefyll]

GARTHWILSON wrote:

reading and using the T1 value in part of your algorithm adds randomness

Along the same lines as Garth's idea, I used to sample the VIA port that accepted input from an ascii keyboard that was part of my setup at the time. The 40-pin keyboard controller chip (visible in the photo) had an RC oscillator and a counter as part of its system for scanning the key matrix. Of course the parallel output would become stable when a key was pressed (also a pulse would appear on a separate strobe line), but when there weren't any keys pressed the parallel output would carry a succession of garbage characters that somehow reflecting the scanning that was in progress.

My RNG involved other factors as well. Like a free-running VIA timer, the garbage character itself isn't random but the jitter in the sample timing tends to scramble things somewhat. I don't recall the recipe I used, but it served the purpose at the time!

-- Jeff

[Klaus2m5]

How about a white noise generator as the base for true random numbers?

http://holdenc.altervista.org/avalanche/

[BigEd]

There's the idea of 'mixing' in random number generators, especially in a crypto context, which is generally rather more involved than just xoring in some other sources of entropy, because you'd like to keep all the bits you have and add in the bits you are getting. A simple xor might cancel out, whereas hashing the two items together usually has the desired effect of every input bit having an effect, and also every output bit being affected by every input bit.

So, if you have some approach to mixing that you feel happy with, you can bring in timings from the outside world (keyboard, network, disk) quite safely and usefully, and you don't even have to reduce them to the few bits of entropy they represent.

You can also mix in from a biased noise source (which is why I mention it) - it's a good way to 'whiten' any patterns which the source might have.

Although almost no-one would need crypto-strength random numbers or mixing, it's at least as good as it needs to be, and if your code finds its way into a gambling machine, it's a good idea.

• stackoverflow: Safe mixing of entropy sources
  Cryptography Stack Exchange: Lightweight cipher using only 8-bit operations

[BigEd]

Looking through old threads, I see Bruce has written something substantial about random number generators for 6502:

• Linear Congruential Pseudo-Random Number Generator Routines

Ref these threads:

• combined Tausworthe PRNGs
  Attempting to code a password secure OS.
  • (which links to this article by the late Lee Davison now found in the wayback machine archive: 6502 8 bit PRNG

)

[sark02]

Back in the day, when 15 year old me was writing little hobby games on the Atari 800XL, my goto RNG was:

Code: Select all

uint8_t next_rnd(void)
{
    static uint8_t rnd;
    rnd = rnd * 5 + 17;
    return rnd;
}

Or, in other words:

Code: Select all

RND:  .BYTE 0

NEXT_RND:
    LDA RND
    LSL A        ; A = RND * 2
    LSL A        ; A = RND * 4
    CLC
    ADC RND      ; A = RND * 5
    CLC
    ADC #17      ; A = RND * 5 + 17
    STA RND
    RTS

If you call this function 256 times, you'll get all 256 possible values. It was good enough for what I was doing at the time.

[bogax]

I like the Batari Basic rand16

It's just a 16 bit LFSR that shifts the two bytes in opposite directions
and XORs them for an 8bit return value

Code: Select all

  lda seedhi
  lsr
  rol seedlo
  bcc noeor
  eor #$B4
noeor
  sta seedhi
  eor seedlo

This is an interesting read hmc-cs-2014-0905.pdf

[White Flame]

If that seed is ever 0000, then it'll stay fixed at that value and never change.

[BigEd]

Thanks for the link to PCG, bogax. Some more reading:

• wikipedia
  HN discussion about a relevant blog post

That blogger, Daniel Lemire, also did a survey:

• Testing non-cryptographic random number generators: my results

One thing we're up against is that most modern work on PRNGs will be for 64 bit machines with barrel shifters and fast multiply and divide. Even if for 32 bit machines, the approaches might not be good for 6502.

Another thing to note: if you just want a stream of random bits, it's a waste to compute 16 or 32 and then just use one bit. Same for two or three bits. Unfortunately to roll a six-sided die you need to take all the bits and reduce them to six cases, because six isn't a power of two.

[sark02]

White Flame wrote:

If that seed is ever 0000, then it'll stay fixed at that value and never change.

True, but I tested bogax's function with an initial seed of FFFF and after 65535 calls it returned every value and then repeated. So as long as you don't initialize it with zero, it'll never land there by itself.

It's a cool little function.