Why is so much salience given to the lower bits? This would ignore very obvious patterns in the middle bits. Would patterns in the middle bits matter? Are there tests based on arbitrary byte-wise permutations, or even just turning a number “inside out” by reversing the higher 32 bits and lower 32 bits?
Robert Dibleysays:
A number of the very early random number generators had obvious patterns in the low bits while appearing to be random in the upper bits – several of them would repeat the same last 3 or 4 bits over and over for ever.
More recent algorithms tend to remove that problem, so it’s perhaps not as significant now, but its wise to check everything just in case a problem has been reintroduced.
For an example of bad random numbers, see if you can find details of the PlayStation 2 hardware random number generator, which generated floating point random numbers in the vector units. This was found to suffer from a very strong pattern, so much so that if you were to take several thousand values, and assign them in groups of three to points in space, you would end up with a series of rotated grid-like layers in space, which could hardly be less random if it tried. Try the same with your current favourite random number generator and see what you get!
While the figure annotation implies that this is the exact implementation used, the surrounding paper implies that it only passed BigCrush using different choices for a, b, and c than the ones in that code snippet.
The code snippet that you tested for xorshift128+ appears to be taken from this paper here (…)
I copied and pasted it from the author’s web site: http://xoroshiro.di.unimi.it/xorshift128plus.c. But it is also identical to Figure 1 in the peer-reviewed paper with the label The xorshift128+ generator used in the tests.
While the figure annotation implies that this is the exact implementation used, the surrounding paper implies that it only passed BigCrush using different choices for a, b, and c than the ones in that code snippet.
Vigna specifically recommends the triple (23, 18, 5) that I have tested, and he recommends against the triples you suggest (a=23, b=17, c=26) which appears first in Table 1:
Table 4 compares the BigCrush scores of the generators we discussed. For xorshift128+ we used the triple 23, 18, 5 (Figure 1). (…) Our choice of triples is based not only on the BigCrush scores and on polynomial weight, but also on an additional datum: the result of POP (“p-value of p-valuesâ€) tests. (…) The triples we suggest for xorshift+ do not fail any POP test (…) but, for example, the first triple listed in Table 1 fails four POP tests.
Summary for v8xorshift128plus lsb 32-bits (bit reverse) (4 crushes):
- #68: MatrixRank, L=1000, r=0: FAIL!! -- p-values too unlikely (eps, eps, eps, eps) -- ALL CRUSHES FAIL!!
- #71: MatrixRank, L=5000: FAIL!! -- p-values too unlikely (eps, eps, eps, eps) -- ALL CRUSHES FAIL!!
- #80: LinearComp, r = 0: FAIL!! -- p-values too unlikely (1 - eps1, 1 - eps1, 1 - eps1, 1 - eps1) -- ALL CRUSHES FAIL!!
Dave Bobkersays:
Can simple modifications not improve the output. What occurs to me is:
1) Load the intial state with 2 64 bit seeds, not 1
2) Load the initial state with 4 64 bit seeds to give 2 states and alternate output between the two
3) “Shuffle” output a la Numerical Recipes say with a table of length 256 or 512.
Have any of these been tried? All of them would add negligible time to execution.
DIVVS·IVLIVSsays:
As far as I know, xorshift128+ was superseded by xoroshiro128+ (XOR/rotate/shift/rotate), with significant improvement in speed (well below a nanosecond per integer) and a significant improvement in statistical quality, as detected by the long-range tests of PractRand.
Albert Chansays:
I tried both xorshift128+ and xoroshiro128+, but they are about the same speed. For my old Pentium 3, xorshift128+
comes out slightly ahead in speed.
TonyB_says:
A new paper out today by David Blackman & Sebastiano Vigna discusses xoroshiro, a new generator called xoshiro and better scramblers, in particular **. For details please see http://xoshiro.di.unimi.it/
xorshift+ and xorshift* have been very much superseded.
Lorenzo Lodisays:
You might be interested to know that very recently the Japanese authors of the Mersenne Twister have found that a simple ‘zooming in’ on xoroshift128+ reveals non-random distributions, and have given passed a damning judgement on this generator:
Hiroshi Haramoto, Makoto Matsumoto, Again, random numbers fall mainly in the planes: xorshift128+ generators https://arxiv.org/abs/1908.10020
Hiroshi Haramoto, Makoto Matsumoto, Mutsuo Saito, Pseudo random number generators: attention for a newly proposed generator https://arxiv.org/abs/1907.03251
They also stress that one should not rely too much on testing suites such as TestU01, PractRand etc. because they are primarily made to reveal faults in already existing PNG. It is too easy to take a ‘bad’ generator which fails TestU01, tweak it a bit and make it pass it, but in so doing deviations from randomness are probably just moves somewhere else where the test suite is not looking. This is, I think what they are saying.
Personally I really see little reason for not using a strong cryptographically secure RNG, such as AES in counter mode (with hardware support), ChaCha8, perhaps ISAAC etc. I think they are fast and slim enough for practically all applications and they have been scrutinised much, much more thoroughly than any ‘ordinary’ RNG, whose randomness is only skin-deep.
Daniel Lemire, Melissa E. O’Neill
Xorshift1024*, Xorshift1024+, Xorshift128+ and Xoroshiro128+ Fail Statistical Tests for Linearity
Computational and Applied Mathematics 350, 2019 https://arxiv.org/abs/1810.05313
Joshua Scholarsays:
This makes me feel a little proud. I just came up with a lagged Fibonacci generator (with carry) for tiny little 8 bit processors, it’s initialized with a kind of xshift, and it passes bigcrunch both regular and bit reversed (it generates one byte at a time, so collect 4 to make a unit for bigcrunch to test).
Why is so much salience given to the lower bits? This would ignore very obvious patterns in the middle bits. Would patterns in the middle bits matter? Are there tests based on arbitrary byte-wise permutations, or even just turning a number “inside out” by reversing the higher 32 bits and lower 32 bits?
A number of the very early random number generators had obvious patterns in the low bits while appearing to be random in the upper bits – several of them would repeat the same last 3 or 4 bits over and over for ever.
More recent algorithms tend to remove that problem, so it’s perhaps not as significant now, but its wise to check everything just in case a problem has been reintroduced.
For an example of bad random numbers, see if you can find details of the PlayStation 2 hardware random number generator, which generated floating point random numbers in the vector units. This was found to suffer from a very strong pattern, so much so that if you were to take several thousand values, and assign them in groups of three to points in space, you would end up with a series of rotated grid-like layers in space, which could hardly be less random if it tried. Try the same with your current favourite random number generator and see what you get!
The code snippet that you tested for xorshift128+ appears to be taken from this paper here http://vigna.di.unimi.it/ftp/papers/xorshiftplus.pdf .
While the figure annotation implies that this is the exact implementation used, the surrounding paper implies that it only passed BigCrush using different choices for a, b, and c than the ones in that code snippet.
Could you reproduce these results with a=23, b=17, c=26? These are the constants listed as the “best” in that paper, as well as the constants used by the V8 runtime (https://v8project.blogspot.se/2015/12/theres-mathrandom-and-then-theres.html) and the constants used in the wikipedia example (https://en.wikipedia.org/wiki/Xorshift#xorshift.2B).
The code snippet that you tested for xorshift128+ appears to be taken from this paper here (…)
I copied and pasted it from the author’s web site: http://xoroshiro.di.unimi.it/xorshift128plus.c. But it is also identical to Figure 1 in the peer-reviewed paper with the label The xorshift128+ generator used in the tests.
While the figure annotation implies that this is the exact implementation used, the surrounding paper implies that it only passed BigCrush using different choices for a, b, and c than the ones in that code snippet.
Vigna specifically recommends the triple (23, 18, 5) that I have tested, and he recommends against the triples you suggest (a=23, b=17, c=26) which appears first in Table 1:
(This is a direct quote from the paper.)
Could you reproduce these results with a=23, b=17, c=26?
Tests are running. Big Crush takes many hours, but I already have the results from PractRand:
So we have a failure. You should expect a Big Crush failure (since statistical tests tend to be redundant).
So, yes, the failure is confirmed:
Can simple modifications not improve the output. What occurs to me is:
1) Load the intial state with 2 64 bit seeds, not 1
2) Load the initial state with 4 64 bit seeds to give 2 states and alternate output between the two
3) “Shuffle” output a la Numerical Recipes say with a table of length 256 or 512.
Have any of these been tried? All of them would add negligible time to execution.
As far as I know, xorshift128+ was superseded by xoroshiro128+ (XOR/rotate/shift/rotate), with significant improvement in speed (well below a nanosecond per integer) and a significant improvement in statistical quality, as detected by the long-range tests of PractRand.
I tried both xorshift128+ and xoroshiro128+, but they are about the same speed. For my old Pentium 3, xorshift128+
comes out slightly ahead in speed.
A new paper out today by David Blackman & Sebastiano Vigna discusses xoroshiro, a new generator called xoshiro and better scramblers, in particular **. For details please see http://xoshiro.di.unimi.it/
xorshift+ and xorshift* have been very much superseded.
You might be interested to know that very recently the Japanese authors of the Mersenne Twister have found that a simple ‘zooming in’ on xoroshift128+ reveals non-random distributions, and have given passed a damning judgement on this generator:
Hiroshi Haramoto, Makoto Matsumoto, Again, random numbers fall mainly in the planes: xorshift128+ generators
https://arxiv.org/abs/1908.10020
Hiroshi Haramoto, Makoto Matsumoto, Mutsuo Saito, Pseudo random number generators: attention for a newly proposed generator
https://arxiv.org/abs/1907.03251
They also stress that one should not rely too much on testing suites such as TestU01, PractRand etc. because they are primarily made to reveal faults in already existing PNG. It is too easy to take a ‘bad’ generator which fails TestU01, tweak it a bit and make it pass it, but in so doing deviations from randomness are probably just moves somewhere else where the test suite is not looking. This is, I think what they are saying.
Personally I really see little reason for not using a strong cryptographically secure RNG, such as AES in counter mode (with hardware support), ChaCha8, perhaps ISAAC etc. I think they are fast and slim enough for practically all applications and they have been scrutinised much, much more thoroughly than any ‘ordinary’ RNG, whose randomness is only skin-deep.
Don’t miss our paper…
Daniel Lemire, Melissa E. O’Neill
Xorshift1024*, Xorshift1024+, Xorshift128+ and Xoroshiro128+ Fail Statistical Tests for Linearity
Computational and Applied Mathematics 350, 2019
https://arxiv.org/abs/1810.05313
This makes me feel a little proud. I just came up with a lagged Fibonacci generator (with carry) for tiny little 8 bit processors, it’s initialized with a kind of xshift, and it passes bigcrunch both regular and bit reversed (it generates one byte at a time, so collect 4 to make a unit for bigcrunch to test).