Linear Feedback Shift Registers (Generating Random Sequences XII)

While working on a project with a student, I had a look at linear feedback shift registers as a mean of generating (pseudo)random values. The principle isn’t very complicated: you select a number of bits in the register and use them to compute one bit value, you shift the register by one position and insert the new bit in the vacant spot.

Typically, the function is merely a series of exclusive ors, which basically computes the parity of the selected bits. This will help us create an efficient implementation—maybe using the compiler intrinsics.

Let’s first convince ourselves that a series of xors are equivalent to computing the parity. If you xor a series of bits together, the result will be one only if there’s an odd number of bits that are 1s, and zero if the number is even. That’s exactly how parity is defined. More precisely, that’s how odd parity is computed (even parity gives 1 when the number of bits set to 1 is even).

Lucky for us, GCC has an intrinsic function __builtin_parity that computes odd parity. To get even parity, we xor the odd parity with 1—this will allow 0 as a state (otherwise it’d be a fixed point, which is now 0xff…f).

Extracting a certain number of bits from the register (the state of the pseudo-random number generator) seems to be a complicated operation until we realize that and-ing the state with a mask with 1 bits in the interesting position will extract the bits just fine for the computation of parity!

Shifting shouldn’t be a mysterious step.

The complete generator therefore fits into one line of code, or almost:

```#include <time.h>
#include <cstdint>
#include <iostream>

class lsr
{
private:

uint32_t selector;
uint32_t state;

public:

uint32_t operator()()
{
uint32_t t=state;

state=((state<<1)
| (__builtin_parity(state & selector)^1)) & mask;

return t;
}

lsr( int bits,
uint32_t s,
uint32_t seed)
: mask((1<<bits)-1), // actually 32-bit safe!
selector(s),
{}
};

int main()
{
lsr a(10,0x204,0); // or time(0));

for (int i=0;i<1024;i++)
std::cout << '\t' << a();
return 0;
}
```

This lovely piece of code generates

```0 1 3 7 14 28 56 113
227 455 910 797 571 118 236 472
945 866 708 393 787 550 77 154
309 618 212 424 849 674 324 648
272 545 66 133 266 533 43 87 174
348 696 368 737 450 901 779 534
45 90 181 362 725 427 855 687
351 702 381 762 500 1000 976
928 832 640 256 513 2 5 10 21
42 85 170 341 682 340 680 336
```

*
* *

The above minimal implementation uses a mysterious value: the selector. The interesting question is now “how do we get a good selector?” The answer is not entirely trivial. You want a selector that will allow the generator to visit every state (except the fixed point, which will be 0xff…f in even parity) exactly once.

Brute-forcing the solutions isn’t that much interesting, but that’s something you can do rather easily. For each registers sizes 2 to 32, the first selectors I found were:

 Bits Selector 2 3 3 5 4 9 5 12 6 21 7 41 8 8e 9 108 10 204 11 402 12 829 13 100d 14 2015 15 4001 16 8016 17 10004 18 20013 19 40013 20 80004 21 100002 22 200001 23 400010 24 80000d 25 1000004 26 2000023 27 4000013 28 8000004 29 10000002 30 20000029 31 40000004 32 80000057

Are those good selectors? Yes, but linear feedback shift registers are limited in very strange ways. For example, if your initial seed is 1, you may see the first values generated be 0, 1, 3, 7, 14, 28, 56, 113, … that’s doesn’t look very random. First, there are no measure of dispersion. The values above merely guaranty that each state (except 0xff..ff) is visited exactly once before starting to repeat over again. I do not know how to measure dispersion meaningfully. Maximizing the difference between consecutive values? Between consecutive residues modulo some number?

To be continued, maybe.