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 mask;
      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),
     state(seed & mask)
   {}
};

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: