Building a 16-bit Linear Congruential Generator

The 16 bit seed version of the Linear Congruential Generator (LCG) is very similar to the 8 bit version in that every time it is called it returns a byte. The big difference is that the seed is 16 bits instead of 8 bits so we will have a longer time before numbers start repeating and a bit more randomness. To get the longer cycle (and more randomness) we need to use the upper byte of the results.

For those of you who haven't read the earlier blog entries in this series or who want a quick refresher, LCG uses the formula $S_n = A*S_{n-1}+C$ for getting the next seed so we are simply multiplying the seed by a constant A and then adding a constant C to the result. We will use 141
for A and 3 for C though other carefully chosen values could be used.

We already have the multiplication which we wrote last fortnight, so now all we have to do is use that multiplication routine and then add a constant to that value. This is very simple code as you can see.

; set up our constants for A and C
.EQU LCG_A 141
.EQU LCG_C 3
; create placeholder for RNG seed
seedLo: .BYTE 0
seedHi: .BYTE 0
; ...
; multiply16x8 setup and code would be put here
; ...

lcg16bit:
; load in the current value of the seed into the multiply registers
LDA seedLo
LDY seedHi
; now multiply by the A constant
LDX #LCG_A
JSR multiply16x8
; add the C constant to the reult
CLC
ADC #LCG_C
BCC lcg16bit_update_seed
INY
lcg16bit_update_seed:
; save the results in the seed
STA seedLo
STY seedHi
; put results in accumulator for return value
TYA
RTS

To test this simply call the random number generator 257 times and look at the sequence of numbers that are generated.

test:
JSR lcg16bit
; now lets do this 256 more times
LDX #0
test_loop:
TXA
PHA
JSR lcg16bit
PLA
TAX
DEX
BNE test_loop
NOP ; using this as easy to find separator
BRK

While this does demonstrate that it is working and gives us a longer sequence than the first method, it is not a very good test. For our needs we don't need statistically sound random number generation, but a simple test like generating randograms would be sufficient for getting a rough idea of how the generator was working. Randograms were covered in an earlier blog post but are essentially a 256 * 256 grid that you plot by taking two random numbers and plotting the point on the graph. This is a good idea but not really implementable on a 64k machine as the minimum size for holding the grid is 65536 bytes and we would still need some way to save the data. However, we have our own emulator so could cheat a bit to get the result. More on this next fortnight.