random - How to do an 8-bit, 16-bit, and 32-bit Linear-Feedback Shift Register PRNG in JavaScript?

Question

I am looking for a PRNG that works in O(1) time and never encounters a duplicate number as you increment through the values. The question Unique (non-repeating) random numbers in O(1)? doesn't get directly answered with an implementation, and it's hard to see how to apply it. One of the best answers as far as I can tell is the Linear-Feedback Shift Register one. I don't quite understand the C code though:

# include <stdint.h>
unsigned lfsr1(void)
{
    uint16_t start_state = 0xACE1u;  /* Any nonzero start state will work. */
    uint16_t lfsr = start_state;
    uint16_t bit;                    /* Must be 16-bit to allow bit<<15 later in the code */
    unsigned period = 0;

    do
    {   /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
        bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) /* & 1u */;
        lfsr = (lfsr >> 1) | (bit << 15);
        ++period;
    }
    while (lfsr != start_state);

    return period;
}

Wondering how you could implement a Linear-Feedback Shift Register PRNG as 3 JavaScript functions: 8-bit, 16-bit, and 32-bit versions which take x as input and return a new x, never encountering a duplicate number until you start over.

Answer 1

This C code implements a Fibonacci LFSR, and looks like it was copied from Wikipedia where it's described in more detail. Briefly, it calculates the next number in a pseudorandom sequence by shifting every bit to the right (lsfr >> 1) while filling the highest-order bit with the XOR product of other bit positions chosen in such a way that the resulting sequence is of maximal length (equal to 2ⁿ?1, where n is the number of bits in the integer). So for example, a 16-bit LSFR has a period of length 65535, and cycles through every 16-bit integer value except zero.

This code can be translated to Javascript quite easily. You just need to bear in mind that an integer of type uint16_t consists of only 16 bits, so anything that gets shifted to bits 16 and above will be lost. Since Javascript integers have more than 16 bits, you'll have to make sure that bits 16 and above are zero before returning the result. You can do this by uncommenting the & 1u part of the expression. (Ignore the u; this just tells the C compiler that 1 is an unsigned integer.)

Having said that, I'm not sure I can recommend this sort of LFSR. If you calculate all the values in the pseudorandom sequence, you'll find that each value is equal to half the previous value with a probability of about 50%. The Xorshift algorithm gives a better spread of numbers while being just as easy to calculate.

I couldn't find any online sources for 8-bit or 16-bit Xorshift functions, so you might want to confirm that the functions below actually generate maximal length sequences before using them.

function xorshift8(x) {
    x |= x == 0;   // if x == 0, set x = 1 instead
    x ^= (x & 0x07) << 5;
    x ^= x >> 3;
    x ^= (x & 0x03) << 6;
    return x & 0xff;
}

function xorshift16(x) {
    x |= x == 0;   // if x == 0, set x = 1 instead
    x ^= (x & 0x07ff) << 5;
    x ^= x >> 7;
    x ^= (x & 0x0003) << 14;
    return x & 0xffff;
}

function xorshift32(x) {
    x |= x == 0;   // if x == 0, set x = 1 instead
    x ^= (x & 0x0007ffff) << 13;
    x ^= x >> 17;
    x ^= (x & 0x07ffffff) << 5;
    return x & 0xffffffff;
}