Random number generator/Linear feedback shift register (advanced): Difference between revisions
Rainwarrior (talk | contribs) (→24 and 32 bit LFSR: lowest 24-bit polynomial is $1B, still searching for lowest 32-bit but $C5 works until then.) |
Rainwarrior (talk | contribs) m (→24 and 32 bit LFSR: ROL ZP x 8 = 40 cycles) |
||
| Line 45: | Line 45: | ||
== 24 and 32 bit LFSR == | == 24 and 32 bit LFSR == | ||
By adding an extra byte or two to the seed variable, and choosing an appropriate polynomial to XOR with, we can extend the sequence length significantly with only one additonal ROL per byte. | By adding an extra byte or two to the seed variable, and choosing an appropriate polynomial to XOR with, we can extend the sequence length significantly with only one additonal ROL per byte (+40 cycles). | ||
This 24-bit version has a sequence length of 16777215: | This 24-bit version has a sequence length of 16777215: | ||
Revision as of 19:29, 11 July 2016
Further commentary on the linear feedback shift register example at random number generator.
Basic version
prng: ldx #8 ; iteration count lda seed+0 : asl ; shift the register rol seed+1 bcc :+ eor #$2D ; apply XOR feedback whenever a 1 bit is shifted out : dex bne :-- sta seed+0 cmp #0 ; reload flags rts
Sacrifice entropy for speed
The iteration count stored in X can be reduced to speed up the generator, at the expense of quality of randomness. Each iteration effectively generators one more bit of entropy, so 8 iterations are needed for an 8-bit random number. If you intend to use fewer bits of the result (e.g. use AND to mask the result), or if you are satisfied with less randomness, you can reduce X, or even parameterize it:
; X as a parameter specifies number of random bits to generate (1 to 8) prng: lda seed+0 @bitloop: asl rol seed+1 bcc :+ eor #$2D : dex bne @bitloop sta seed+0 cmp #0 rts
Alternatively this loop could be unrolled with 8 entry points, saving the need to use X or load it as a parameter.
Because the 16-bit LFSR has a repeating cycle of 65535 values, groups of 6, 5, or 3 bits will reduce the length of its output sequence. This should be avoided, if possible.
24 and 32 bit LFSR
By adding an extra byte or two to the seed variable, and choosing an appropriate polynomial to XOR with, we can extend the sequence length significantly with only one additonal ROL per byte (+40 cycles).
This 24-bit version has a sequence length of 16777215:
.zeropage seed: .res 3 ; 24-bit .code prng: ldx #8 lda seed+0 : asl rol seed+1 rol seed+2 bcc :+ eor #$1B : dex bne :-- sta seed+0 cmp #0 rts
This 32-bit version has a sequence length of 4294967295:
.zeropage seed: .res 4 ; 32-bit .code prng: ldx #8 lda seed+0 : asl rol seed+1 rol seed+2 rol seed+3 bcc :+ eor #$C5 : dex bne :-- sta seed+0 cmp #0 rts
