Only certain tap settings yield the maximal length sequences (MLS) of (2N-1). Each binary delay register can be expressed as power of 2 in the formula and may used for feedback with/without inversion or feed-forward, using XOR gates combined to create the mathematical algorithm. $39, $2D, and $C5 are chosen because they contain the minimum number of bits, in a compact arrangement that allows a fast overlapped computation.The choice of which taps to use in Linear Feedback Shift Registers (LFSR) determines how many delayed registers, N are included in a sequence of pseudorandom generator (PRG) values before the sequence is repeated. Sty seed+3 finish rotating byte 2 into 3Ī note about the chosen polynomials: several XOR-feedback values are available that will produce a maximal-length LFSR period. Ldy seed+2 will move to seed+3 at the endĮor seed+0 combine with original low byte Sty seed+2 finish rotating byte 1 into 2 Ldy seed+1 will move to seed+2 at the end (One XOR for each feedback bit.) With some careful rearrangement this can do 8 iterations at once very efficiently. With an XOR-feedback that contains only four bits, we can shift and feed back 8 bits at once in a more complex overlapped operation that essentially applies 4 16-bit XOR operations to the lower two bytes of the seed. This 32-bit version has a sequence length of 4294967295: 23 bytes, 213-221 cycles.Įven longer sequences are possible, but it's not likely to be practical, as it would already take approximately 7 days for an NTSC NES to complete this 32 bit LFSR cycle if doing nothing else.
This 24-bit version has a sequence length of 16777215: 21 bytes, 173-181 cycles. Y as a parameter specifies number of random bits to generate (1 to 8)Īlternatively this loop could be unrolled with 8 entry points, saving the need to use Y or load it as a parameter.īy 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).
use AND to mask the result), or if you are satisfied with less randomness, you can reduce Y, or even parameterize it: If you intend to use fewer bits of the result (e.g. Each iteration effectively generators one more bit of entropy, so 8 iterations are needed for an 8-bit random number.
The iteration count stored in Y can be reduced to speed up the generator, at the expense of quality of randomness. Eor #$39 apply XOR feedback whenever a 1 bit is shifted out
0 kommentar(er)
