Tag Archive for state of sin

Xorshift pseudorandom number generator

In 2003, George Marsaglia published a pseudorandom number generator based on repeated shift and XOR operations, a relative of the linear feedback shift register generators. The basic 3-shift PRNG is:

int xorshift() {
    y ^= (y << a);
    y ^= (y >> b);
    return y ^= (y << c);
}

With y seeded with any non-zero starting value. The generator will never produce zero, which is something to be careful of, but with the right values for a, b, and c, will cycle through all non-zero values. If only a subset of the bits are used, a generator with the full period results where zeros do occur, though not as frequently as the other values in the cycle: if you take 6 bits from an 8 bit generator, you will get each non-zero 6-bit number 4 times per cycle, and only 3 zeros. Alternatively, you can simply subtract 1 from the output, and take the usual approaches to obtaining the desired range without unacceptable bias.

The published generators I've found all use 32 bit values or greater, but sometimes something simpler and smaller is needed. Here is the C code for the generators I have been testing. Note that they have been verified to be full cycle and to give reasonably random-looking results, but little more...I assume that nobody needing high quality random numbers will use such a short-period PRNG, but will use the published 32, 64, or 128 bit versions, or another generator altogether.

static uint8_t y8 = 1;
static uint16_t y16 = 1;

// returns values from 1 to 255 inclusive, period is 255
uint8_t xorshift8(void) {
    y8 ^= (y8 << 7);
    y8 ^= (y8 >> 5);
    return y8 ^= (y8 << 3);
}

// returns values from 1 to 65535 inclusive, period is 65535
uint16_t xorshift16(void) {
    y16 ^= (y16 << 13);
    y16 ^= (y16 >> 9);
    return y16 ^= (y16 << 7);
}

Its simplicity and avoidance of operations such as multiplication and division makes it particularly well suited for hardware generation. Unfortunately, it's an imperfect fit to larger AVRs: while it requires little memory, even the simple-appearing one-byte shifts for xorshift8 require several instructions to perform on an AVR, so on devices with the multiply instruction, it is a fair bit slower to compute than a linear congruential generator. However, for those devices that lack the hardware multiplier, there may be notable size and speed benefits. Larger devices with barrel shifters might also benefit (ARMs in particular, due to their ability to "fold" shifts into data-processing instructions), but devices with such instructions are also likely to be better at handling other PRNGs. There is a considerable complexity benefit for hardware or FPGA implementations, and it may still be of use in AVRs and other small microcontrollers as a simple PRNG that avoids some of the problems that LCGs have, such as poor randomness in the low bits, while not being as memory-hungry or as computation-intensive as algorithms like the Mersenne Twister.

These aren't the only choices for a, b, and c that work. For 8 and 16 bit generators, it's simple enough to perform a brute force search for possible combinations. There are 24 full-cycle 8-bit generators:

(1, 1, 2) (1, 1, 3) (1, 7, 3) (1, 7, 6) (1, 7, 7) (2, 1, 1)
(2, 5, 5) (3, 1, 1) (3, 1, 5) (3, 5, 4) (3, 5, 5) (3, 5, 7)
(3, 7, 1) (4, 5, 3) (5, 1, 3) (5, 3, 6) (5, 3, 7) (5, 5, 2)
(5, 5, 3) (6, 3, 5) (6, 7, 1) (7, 3, 5) (7, 5, 3) (7, 7, 1)

And 60 16-bit generators:

(1, 1, 14) (1, 1, 15) (1, 5, 2 ) (1, 7, 4 ) (1, 7, 11) (1, 11, 3 )
(1, 15, 6 ) (1, 15, 7 ) (2, 5, 1 ) (2, 5, 13) (2, 5, 15) (2, 7, 13)
(2, 7, 15) (3, 1, 12) (3, 1, 15) (3, 5, 11) (3, 11, 1 ) (3, 11, 11)
(3, 13, 9 ) (4, 3, 7 ) (4, 7, 1 ) (4, 11, 11) (5, 7, 14) (5, 9, 8 )
(5, 11, 6 ) (5, 11, 11) (6, 7, 13) (6, 11, 5 ) (6, 15, 1 ) (7, 1, 11)
(7, 3, 4 ) (7, 9, 8 ) (7, 9, 13) (7, 15, 1 ) (8, 9, 5 ) (8, 9, 7 )
(9, 7, 13) (9, 13, 3 ) (11, 1, 7 ) (11, 3, 13) (11, 5, 3 ) (11, 7, 1 )
(11, 11, 3 ) (11, 11, 4 ) (11, 11, 5 ) (12, 1, 3 ) (12, 3, 13) (13, 3, 11)
(13, 3, 12) (13, 5, 2 ) (13, 7, 2 ) (13, 7, 6 ) (13, 7, 9 ) (13, 9, 7 )
(14, 1, 1 ) (14, 7, 5 ) (15, 1, 1 ) (15, 1, 3 ) (15, 5, 2 ) (15, 7, 2 )

http://www.jstatsoft.org/v08/i14/paper
http://www.jstatsoft.org/v11/i04/paper