XOR with another value after every round of xorshift RNG?

Question

Xorshift and all LFSR type generators will grind to a screeching halt and do nothing if one were to seed it with an all-zeros state. It appears(if there isn't a bug in my test), that the following function:

y = one_xorshift_round(y)
y = y ^ key

will be resistant to that kind of lockup, because any non-zero state of y will produce a change to some random value, and any state that is zero will be XORed to something else by the key. If the key causes it to land on a zero, it will fix it next round.

I would imagine you would also get the added benefit of every "key" value producing a different sequence.

My application is an Arduino library that needs statistically random numbers that do not need to have any cryptographic strength at all, but cannot just repeat the same cycle over and over again. What I want to do is use the current count of microseconds since the board was powered on as the key, which should add a bit of entropy to the RNG every time it is used(due to uncertainties in the exact timing of things caused by user inputs and the like), and also cause the random sequence to be different over time, sortof artificially faking having a larger period.

My question is, is there some value of key, or simple pattern of variable key, that would cause the XORSHIFT generator to do something bad, like enter a short cycle? I'd imagine the math to actually figure it out would be very complicated but maybe someone has a reference to a paper or soomething with a similiarly modified RNG?

Thanks!

Edit, additional info: my first reaction to the issue of the all zeros state was just to add 1 to the state every round, but I found that adding a constant to the state reduced the period by an amount that varied with the constant but did not seem to have any simple pattern.

Answer 1

The simplest case where the key would result in a short cycle is where the key is the exclusive or one value and its successive value from the original generator. This would have the effect of resetting the state to its previous value, so that it could only ever produce one output.

If that key value was the same for many different output pairs from the original generator then that would represent a gross failure in randomness tests, so it's more likely that there are many different values that would effectively step one stage back in the cycle at different points in that cycle.

So it's probably fair to assume that many values for your key could shorten the period of the generator by eventually trapping it in a single-value orbit. Then there are the more complex cases resulting in longer orbits which still aren't the full period, but these are much harder to think through.

What you might want to do instead is to collect your entropy separately and use it to temper the output from your PRNG without spoiling the qualities of the PRNG itself. Eg.,

void add_entropy(uint32_t more)
{
    entropy = one_xorshift_round(entropy + more);
}

uint32_t rand(void)
{
    y = one_xorshift_round(y);
    return one_xorshift_round(y + entropy);
}

Answer 2

I wouldn't fiddle too much with a random generator (like altering arbitrarily the state space) because its good statistical properties might vanish.

Testing that the seed is not all zeroes is not bad at all: this is what is done in every generator of this kind. If you want inject entropy, just xor your entropy bits over the state space and if you get all zeroes just put in some constant. If the state space is large enough the probability is so low that what you put in is not relevant. Many published generators use the name of the generator (as a sequence of ASCII value) to seed the generator in that case! :)

I would however suggest that you try some 64-bit variant such as xorshift*/xorshift+ as they have much better statistic properties than a pure xorshift generator. You can find an up-to-date report at http://prng.di.unimi.it/