April 2016 Archives

Last time we took a look at linear feedback shift registers, or LFSRs, which produce pseudo random bits by shifting a buffer of them to the right, with the rightmost becoming both the output and the leftmost bit which being combined with a subset of the bits, known as taps, using an exclusive or operation.
We saw that despite looking completely different to the linear congruential generators that we covered a few posts ago they are in fact rather similar to them, albeit involving multiplication and remainder operations involving polynomials rather than integers.
Unfortunately, another thing that LFSRs have in common with linear congruential generators is that it is extremely difficult to set them up so that they generate sequences of bits that are as close to random as possible. Thankfully, there are those who've gone to the trouble of finding decent choices for the taps for us and so all that we need to concern ourselves with is implementing them, which we shall do in this post.

We have seen how we can approximate random variables with linear congruences of the form

  x_i+1 = a × x_i + c % m

where x % m is the remainder of the integer division of x by m. If we are careful with our choices of the seed x₀, the multiplier a, the increment c and the modulus m then they can generate sequences of pseudo random numbers that, whilst wholly deterministic, pass many of the statistical tests for randomness.
These are not the only kind of recurrences that we can use to generate pseudo random numbers, however.