[PolishedTurd]

I am trying to write a random number generator for the NES that will work on any ROM. The goal is to be able to pass the max value as a parameter via a register, and receive the random number in another register. For example, if I pass in 10 (decimal), I expect to get a value between 0 and 9.

My strategy is to sample a regularly changing number that is larger than the input arg (e.g., a timer that decrements every cycle and wraps at 0), and subtract the input successively until the value is less than the input (modular arithmetic). But I'm not aware of a ROM-independent way to get the regularly changing value. It's not the end of the world to hunt for a timer register in every ROM I work with, but I'm wondering if there is a better way. For example, I vaguely recall someone sampling the noise register for random values, but this doesn't seem reliable.

[Disch]

pRNGs typically work on a mathematical algorithm.  The most basic might look something like this:

Code: [Select]

out = (in * A) + B
Where A and B are moderately sized prime numbers.  'out' is the generated random number (which can be later scaled down to a specific range), and 'out' is also used as 'in' for the next iteration.

(Note:  this is extraordinarily simplistic -- modern RNGs are much more complex.. there's an entire field of study dedicated to this shit.  But I'm assuming you don't need a great one)

All you need from there is an initial value for 'in' (known as the "Seed").  An easy value for the seed is the system clock at time of program launch (if available) -- or on machines where that's not possible (like NES/SNES/etc), the count of frames between power on and the first user input is sometimes used, since that's unlikely to be identical between games.


Either way, an RNG consisting of both a 'generate' function and a 'seed' function is pretty much the universal norm, and trying to make one without a separate seed function will pretty much guarantee your RNG will suck.  My advice is to have these two functions in your RNG and leave it up to the game that uses it to figure out how to seed it properly.

EDIT 2:
So.. "hunt down the timer in each game" is what I'm recommending in this case.  The NES doesn't really have any readable register that will produce something pseudo-random, so you're SOL as far as that's concerned.
/EDIT 2



As for scaling the number down, rather than looped subtraction (which can be painfully slow if the number is small), you might consider multiplying up by the scalar and then dropping the low byte(s):

Code: [Select]

out = rng_output * scalar / max_possible_rng_output_plus_one
Example: if your RNG is single byte and produces values 0-255, 'max_possible' would be 256.  And if you want a value between 0-9, 'scalar' would be 10.  Dividing by 256 here is trivial (just drop the low byte), and this ensures output that is less than the scalar:

255 * 10 / 256 = 9




EDIT:

Also for systems like the NES where multiplication is a little expensive and the RNG period is going to be low anyway, the RNG computation could be replaced with a 256-byte lookup table that contains the generated sequence.

[jonk]

See: RNG for NES. Found quickly with google. LFSRs are a reasonable alternative to linear congruential generators (LCGs.) However, neither are particularly fast and none of that addresses your desire to specify the upper end of a range of values where you would want, I imagine, a uniform distribution, as well. But converting a linear distribution over one range (the range of the generator, which is typically a symbol space size based on a power of 2) to another range (your specified range) involves yet another multiplication of some kind to achieve. So, avoiding multiplication is probably going to fail. If you only had one range to work with, you could design an LCG to provide exactly that range and thus avoid making this into two steps, both involving multiplication, by combining them to make it into one such step. But since I imagine your range is variable, depending upon purpose, you probably cannot avoid the re-mapping efforts.

(Interesting juxtaposition between the title's mention of x86 and the content's discussion of the NES.)

[bruddogtecmo]

If you could limit your random limiting to multiples of 15 or ranges that could be bitmasked you could do something like this at least as far as limiting the random range once you have the number.

Example limit random number to 0-15

LDA randomNum
AND maxvalue

random = 0xF5 AND with 0x0F = 0x05

Example  limit random number to 0 to 3

LDA randomNum
AND maxvalue

random = 0x59 AND with 0x03 = 0x01 

[PolishedTurd]

See: RNG for NES. Found quickly with google.

(Interesting juxtaposition between the title's mention of x86 and the content's discussion of the NES.)

You're right; sorry about that. I searched for random number generation here and saw a post about Final Fantasy and RNG, but I assumed they were talking about the "range" attribute of a character. And I meant 6502, not x86. Must've forgotten to take my smart pills again, although I think somebody switched them to jelly beans long ago.

LFSR is a clever concept, and treating bits as polynomial coefficients is yet another layer of ingenuity. The algorithm looks so elegant; I'll have to try it.

I've already scratched up my original algorithm, so I can run a comparison and see how my primitive implementation stacks up.

@Disch I was having a hard time coming up with something as straightforward as sampling a timer. For all your experience, I'm glad it gets your imprimatur as well.

I appreciate the advice about scaling too. I'll run some tests and report what I find.

[PolishedTurd]

I am circling back to this. I have found some elegant algorithms for RNG in 6502, but I am struggling with the part about scaling. Is it truly a uniform distribution to simply AND the RNG output with the upper limit operand, as bruddogtecmo says? It seems reasonable and very efficient, but I would like to test it.

Disch's scaling algorithm makes perfect sense algebraically, but doesn't dropping the low byte mean if the product of the upper limit operand and RNG output is less than 256, it will always scale as 0? It doesn't seem right.

But in either case, I could use a suitable test environment to run these algorithms by the thousands and plot the output. Can someone recommend a good free utility?

[Disch]

I am circling back to this. I have found some elegant algorithms for RNG in 6502, but I am struggling with the part about scaling. Is it truly a uniform distribution to simply AND the RNG output with the upper limit operand, as bruddogtecmo says? It seems reasonable and very efficient, but I would like to test it.

If the RNG output is uniform 0-255, then yes -- ASSUMING you are ANDing all low bits with no gaps.

IE:  This only works with power-of-2 ranges (AND with power-of-2 minus one)

Code: [Select]

AND #$3F  ; <- Good -- $40 is a power of 2, $3F is power-of-2 minus one
AND #$3E  ; <- BAD -- will not work, $3F is not a power-of-2

Basically you're just dropping the high bits.

Disch's scaling algorithm makes perfect sense algebraically, but doesn't dropping the low byte mean if the product of the upper limit operand and RNG output is less than 256, it will always scale as 0? It doesn't seem right.

Yes, output less than 256 would be zero.  That is desired behavior.

You can plug in some numbers to see how it'd work.  Say you want a number between 0-2

Code: [Select]

(all numbers in hex)

RNG output    |  multiply by 3  |  drop low byte   |  odds of result
---------------------------------------------------------------------
00 to 55      |  0000 to 00FF   |  00              |  56 / 100
56 to AA      |  0102 to 01FE   |  01              |  55 / 100
AB to FF      |  0201 to 02FD   |  02              |  55 / 100

As you can see, you have SLIGHTLY higher odds of hitting the low numbers, but it's as uniform as possible.  That bias towards lower numbers increases as your range gets higher.  This is easy to see with something like a range of 0-254, where odds of getting zero becomes twice as likely as getting any other number.

Only way I can think of to get TRULY uniform numbers (in a non-power-of-2 range) would be to conditionally reroll the RNG on certain results.  IE:  if you want 0-254, then you'd reroll if the RNG produced 255.  But that's tough to generalize in 6502 and would be time consuming.

EDIT:

Nevermind, rerolling wouldn't even work.  Since the pRNG is just a repeating sequence, this would just widen the window of the next value in the sequence.  IE, rerolling on 255 would just improve the odds of getting whatever number follows 255 in the sequence, since there are now 2 ways to produce it.

Rerolling only works if the RNG is truly random -- like with actual dice or something.

So yeah.. I have no idea how you'd get perfectly uniform distribution here.  So multiply-and-drop-low-byte approach is going to be as good as anything.

/EDIT


EDIT 2:

Or maybe I'm wrong and rerolling would work?  I don't know, I'm not confident in either answer.  =x

/EDIT 2

But in either case, I could use a suitable test environment to run these algorithms by the thousands and plot the output. Can someone recommend a good free utility?

You could whip something up in python, I suppose.  There are even online python interpreters, so you don't even need to install it.

Here's the first one I found:  https://repl.it/languages/python3

Dunno if you can use a plotting library with that, though, but you could print the results out as text easily enough.  If you have Python installed then you can probably get the matplotlib library.

[Raeven0]

EDIT:

Nevermind, rerolling wouldn't even work.  Since the pRNG is just a repeating sequence, this would just widen the window of the next value in the sequence.  IE, rerolling on 255 would just improve the odds of getting whatever number follows 255 in the sequence, since there are now 2 ways to produce it.

Rerolling only works if the RNG is truly random -- like with actual dice or something.

So yeah.. I have no idea how you'd get perfectly uniform distribution here.  So multiply-and-drop-low-byte approach is going to be as good as anything.

/EDIT


EDIT 2:

Or maybe I'm wrong and rerolling would work?  I don't know, I'm not confident in either answer.  =x

/EDIT 2

The nonuniformity due to re-rolling diminishes rapidly with cycle length.

[Bisqwit]

If you need to do division / modulo (or even just multiplication), here is an article I have written that may be of help. https://bisqwit.iki.fi/story/howto/bitmath/

[Trax]

I'm not particulary knowledgeable in random number generation, but my first instinct for the problem of non power of 2 ranges would be this: assuming you start with an acceptable 00-FF random value, repeatedly subtract the length of your desired range (e.g., for 0-9, use 10, decimal) until you reach a number under that value. You will end up with 0-9 all the time, but I can't say if the final result will be reasonably uniform with a larg enough sample. However, with lower ranges, it may become quite costly in terms of CPU cycles. And even more so if you're using multiple bytes.

[Bregalad]

This will obviously lead to non-uniform results : In that specific case (using a 8-bit random value as a source of a random number in the range 0-9), you will get 0-5 more often than 6-9; Because you'd get 0-5 if the RNG triggered 250-255; so there's a 1/25 supplementary chance of them happening.

The only simple way to have uniform result is to do a RNG for the upper power of 2 (in this case, 16 with 4-bit RNG); and re-trigger the RNG if the result is outide of the range (in this case 10-15).

[PolishedTurd]

I ended up finding some truly elegant algorithms online that seemed to satisfy (practically if not academically) the problem of uniform distribution for any input operand up to, say, 32. If I recall, it involved integer division and some clever rounding to get "close enough."

Unfortunately, real life caught up with me pretty hard and I had to table the project. Pretty sure I kept my notes though, and I'd love to get back to it.

I'll look for them at the next opportunity and post what I found.

[tertu]

Here's something that I found that doesn't need division. It's pretty much what Bregalad was suggesting.

Code: [Select]

random_in_range:
  sta scratch
  clc
  sbc #1
  ora #1
  ldx #$FF
  ;determine which mask to use by counting leading zeroes
  @count: inx
  rol a
  bcc @count
  ;loop until random <= range-1
  @try: jsr random
  and mask_bytes, x
  cmp scratch
  bcs @try
  rts
mask_bytes: .db $FF, $7F, $3F, $1F, $0F, $07, $03, $01

EDIT: As other people have said, if the period's too short this can cause problems, but there are algorithms you can use that fit pretty nicely on the 6502 and have periods on the order of 2³², which is probably long enough that it's fine.