Random number generation

[JamesD]

This articles shows several approaches to random number generation.

I've seen the topic mentioned several times on the forum so I thought people might find it interesting.

https://www.codeproject.com/Articles/1190459/Random-Number-Generation-Methods

 

[carlsson]

I just skimmed the article, but it seems to me it is more about how to extract different types of distributions from a known good random number generator, not how to construct a RNG or even PRNG. While that might be interesting, most of the times people get stuck at the first hurdle, how to get any sort of random numbers at all, even if it is a straight distribution from MIN to MAX within a fixed range.

 

For making your own PRNG, often the approach of using an XOR algorithm is mentioned as the simplest, cheapest method though not at all cryptographically strong or secure. Earlier this year I came across an algorithm lifted from the game Defender of the Crown, which uses a pool of 15 seeds that get replaced for each call. The algorithm only requires the ability to add values together and store those in an array, so no need for bit manipulation. As a benefit, this type of PRNG seems to have a period of ~1 million and may return 0 as a random value, compared to XOR in a 8-bit environment which would loop after 256 values.

 

In 6502:

 

rnd    ldy index
       ldx index
       dex
       bpl nowrap
       ldx #14
 
nowrap clc
       lda seeds,y
       adc seeds,x
       sta seeds,y ; Your PRNG value is now in A
       stx index
       rts
 
index  .byte $01
seeds  .byte $f1,$ae,$54,$5a, $e4,$a5,$39,$9d, $13,$60,$a3,$1c, $47,$ad,$6b

In some kind of BASIC:

 

1 DIM SE(15):LET SE(1)=241:LET SE(2)=174:LET SE(3)=84:LET SE(4)=90
2 LET SE(5)=228:LET SE(6)=165:LET SE(7)=57:LET SE(=157:LET SE(9)=19
3 LET SE(10)=96:LET SE(11)=163:LET SE(12)=28:LET SE(13)=71:LET SE(14)=173
4 LET SE(15)=107:LET RY=2:LET RX=2
15 LET RX=RX-1:IF RX<1 THEN LET RX=15
20 LET TMP=SE(RY)+SE(RX):IF TMP>255 THEN LET TMP=TMP-256
25 LET SE(RY)=TMP:LET RY=RX
30 PRINT TMP;:GO TO 15

Try it, you might like it!

 

(Edited because the editor in BBCode mode cuts away pieces of text below certain elements)

Edited June 9, 2017 by carlsson

[Thomas Jentzsch]

I wonder why LFSRs are not mentioned.