May 2016 Archives

Let's Twist Again

In the last few posts we have been looking at linear feedback shift registers, or LFSRs, which generate random bits from a buffer by taking the rightmost bit as the output, shifting the buffer one bit to the right and, if the output is one, applying an exclusive or operation with a set of bits known as taps. Since the leftmost bit is always one of the taps, they effectively shift the output bit back into the leftmost bit of the buffer.
We saw that despite looking completely different to the congruential generators that we covered earlier, they are surprisingly similar, not least in that we must be extremely careful when setting them up if we want to generate sequences of bits that take as long as possible to enter into a cycle.
Finally, we noted that it was possible to generalise LFSRs so that they generate numbers rather than bits, which we shall do in this post.

Full text...