Xorshift
[1] They are a subset of linear-feedback shift registers (LFSRs) which allow a particularly efficient implementation in software without the excessive use of sparse polynomials.
[3] For execution in software, xorshift generators are among the fastest PRNGs, requiring very small code and state.
Because plain xorshift generators (without a non-linear step) fail some statistical tests, they have been accused of being unreliable.
[6] For general purpose, the scrambler ** (pronounced starstar) makes the LFSR generators pass in all bits.
[1] All xorshift* generators emit a sequence of values that is equidistributed in the maximum possible dimension (except that they will never output zero for 16 calls, i.e. 128 bytes, in a row).
[10]: 7 In fact, a reduced version with only 40 bits of internal state passes the suite, suggesting a large safety margin.
Vigna[9] suggests the following xorshift1024* generator with 1024 bits of state and a maximal period of 21024−1; however, it does not always pass BigCrush.
xorshiftr+ (r stands for reduced; reads "xorshifter plus") generator was mainly based on xorshift+ yet incorporates modifications making it significantly faster (especially on lightweight devices) and more successful in randomness tests (including TestU01 BigCrush suite) compared to its predecessors.
The variable sizes, including the state, can be increased with no compromise to the randomness scores, but performance drops may be observed on lightweight devices.
xoshiro256++ is the family's general-purpose random 64-bit number generator.xoshiro256** uses multiplication rather than addition in its output function.
It is worth noting, however, that the output function is invertible, allowing the underlying state to be trivially uncovered.
xoroshiro128+ also exhibits a mild dependency in the population count, generating a failure after 5 TB of output.
Instead of perpetuating Marsaglia's tradition of xorshift as a basic operation, xoroshiro128+ uses a shift/rotate-based linear transformation designed by Sebastiano Vigna in collaboration with David Blackman.
The authors of xoroshiro128+ acknowledge that it does not pass all statistical tests, stating This is xoroshiro128+ 1.0, our best and fastest small-state generator for floating-point numbers.
[21]These claims about not passing tests can be confirmed by running PractRand on the input, resulting in output like that shown below: Acknowledging the authors go on to say:
We suggest to use a sign test to extract a random Boolean value[21]Thus, programmers should prefer the highest bits (e.g., making a heads/tails by writing random_number < 0 rather than random_number & 1).
