6502.org

So are these routines really 'shuffle' with a completely flat distribution?
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

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

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).

Note that Butterfield's statement (on p. 172) that 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.

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.

Yes, I used to do basically that. My 8 bit random number generator used to look more or less like this: Fast and random, but not particularly rigorous.

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

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

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

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

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

)

Back in the day, when 15 year old me was writing little hobby games on the Atari 800XL, my goto RNG was:
Or, in other words: 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.

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

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

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

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.

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.