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.