Testing 6502 Random Number Generators

The routine for testing the random number generator (RNG) is interesting. We want to generate 65536 random numbers so a nested loop is the obvious solution to this problem, but we also need to use the registers. Pushing the state of the loops to the stack before making the call to the RNG is the obvious solution. To improve the efficiency, which really is not needed for test code like this, I did the pulls separately so that only the inner most loop needs to be pulled all the time while the outermost loop only gets pulled from the stack when the inner most loop has ended.

JMP test
; variable declaration goes here
FakeRNG:
; muck up y just to make sure outer loop code works
LDY #99
; Use X to increment value in accumulator and mess up X
TAX
INX
TXA
; This RNG just increments value of accumulator - not very random
RTS
test:
; looping information stored as bytes on stack
LDA #0
PHA
PHA
test_inner_loop:
; this would be a call to the RNG being tested
JSR FakeRNG
; our randogram emulator uses nop to add the value of A
; to the list of random number that have been generated.
NOP
; Handle the inner loop
PLA
TAX
DEX
BEQ test_outer_loop
; this will be reached if outer loop not done
test_inner_loop_adj:
TXA
PHA
JMP test_inner_loop
test_outer_loop:
; Handle outer loop
PLA
TAY
DEY
BEQ done
; this will be reached only if outter loop still going
TYA
PHA
JMP test_inner_loop_adj
done: 
BRK

The test framework includes a simple test generator that simply returns the value in the accumulator incremented by one while mucking up the x and y registers to verify that the loop code is working properly. This will, when ran with the test, cause 1,0,255,254... to be generated which will result in a dotted line on the randogram as can be seen.

Applying the test framework to the two existing generators is trivially easy. We simply need to replace the jsr call to the appropriate random number generator. The results of the 8 bit generator are obviously not that great. If you were to look at the order that the numbers were generated, this is not too bad, the real problem is that there is only a single iteration of the numbers and once all the numbers have been picked, the loop repeats.

Going with 16 bits and taking the upper bits should solve this problem so lets take a look at the randogram for this generator

Not too shabby but a pattern can still be seen. The PCG generator, at least the simplest permutation of it, is very simple to add so next fortnight we will implement that and see how well it compares to our 16-bit LCG generator.