Talk:Xorshift

Untitled

The last sentence should be changed. According to Brent (ref 2) xorshift RNGs are a type of LFSR, which are not cryptographically secure. I suggest "The parameters must be chosen carefully to provide good equidistribution and other properties[3]", which is how I read the Panneton/ L'ecuyer paper. — Preceding unsigned comment added by 24.234.175.101 (talk) 17:50, 16 May 2012 (UTC)

Copyright

The algorithm given in our article is taken straight from the paper cited. I don't think we can claim it is GFDL-compatible without first checking with the author. --Doradus (talk) 14:30, 19 November 2009 (UTC)

I'm not sure why the example was written in 'C' when assembly language (for any microprocessor) would have been so much more intelligible, and better received. In any case, the example would be more informative if it were changed so the argument being operated on (that is, encrypted) is a very long series of null bytes. Dexter Nextnumber (talk) 22:01, 25 December 2009 (UTC)

You cannot copyright just an idea (although you could patent it) and the code given is a very straightforward implementation. I don't think copyright could apply to something as simple and straightforward as this, since anyone implementing the algorithm would have likely written the exact same code. — Preceding unsigned comment added by 82.139.81.0 (talk) 14:48, 2 January 2014 (UTC)

Lmao 134.53.89.169 (talk) 18:51, 18 April 2024 (UTC)

I don't know how assembly would be more intelligible. I've got a crappy JavaScript implementation here if we want to use something like it. Protonk (talk) 17:01, 2 January 2014 (UTC)

Indeed, the claim is absurd. -- 72.194.23.121 (talk) 09:20, 26 July 2020 (UTC)

Period length

According to the article, the period length is 2^128 − 1.

The -1 term is because 0 yields 0. Because the period cannot be longer than the number of numbers usable as internal states, and 0 isn't usable because it won't result in a long sequence.

According to the German version of this article, there are some other numbers that result in extremely short sequences. Those numbers therefore also aren't usable in this sense; they aren't part of the long sequence.

If true, the given sequence length is wrong.

If false, the German article must be corrected. — Preceding unsigned comment added by 82.139.81.0 (talk) 14:39, 2 January 2014 (UTC)

• 2^128 − 1 is the maximal period. I've updated the article to note this (and linked the reference which explores parameters which result in short periods). I don't know of a good way to articulate how to choose parameters for long periods without adding a longer section on theory (though one should be added in time). Protonk (talk) 16:31, 2 January 2014 (UTC)

3rd paragraph needs some love

"Because plain xorshift generators (without non-linear step) fail a few statistical tests, they have been accused of being unreliable[6] and not suitable for cryptographic purposes. However, considering the previous paragraph, it is highly debatable whether this is a fair objection or whether the authors even bothered to read the original papers carefully." First the authors of the referenced paper was able to spot a typo in Marsaglia's paper (section 5, page 9), so it's likely they did read it carefully (also, quoting from the conclusions, "To get rid of the linear structure of the output sequence and further improve the statistical robustness, these xorshift generators could be combined with other RNGs from different classes..." :)

Second, this paragraph conflates legitimate criticism (about the strength of xorshift generators) with... invented criticism? Xorshift generators have never been accused of "being not suitable for cryptographic purposes", for the very simple reasons that they are not (and were never meant to be) suitable for cryptography - this very article says so in the 2nd paragraph ("Xorshift generators are among the fastest non-cryptographic random number generators").

Useurandom (talk) 20:06, 2 July 2014 (UTC)

32-bit code for xorshift1024* and xorshift128+

The best variants of this according to Sebastiano Vigna's research at [1] are xorshift1024* (lowest # of randomness failures and longer period than xorshift128+), and xorshift128+ (faster than xorshift1024* with less state space required), both of which score at the top of the rankings for lowest number of randomness failures as well as speed, and both of which pass ALL of the Test001 suite's BigCrush tests. So when it comes to fast random number generators whose results are quite random, with short readable code, those 2 random number generators can't be beat, at least not by anything I know of.

The problem is, Sebastiano Vigna has implemented them as 64-bit random number generators that require 64-bit variables. (And his code didn't work with Microsoft Visual C++ but I fixed that by using #ifdefs and such so now it's compatible with Microsoft Visual C++ 6.0 and later.) But anyway, some machines and compilers don't have 64-bit support so it would be nice if someone implemented 32-bit versions of xorshift+ and xorshift*, which would use 32-bit integers for their variables and output. I am not sure what the optimal parameters or state size would be for xorshift+ or xorshift* on with 32-bit variables. Using the 64-bit versions of those you'd have to discard half the bits of the returned value to get a 32-bit return value to use in an otherwise 32-bit program (so calculating a 64-bit value you'll only use half of is a waste), and even assuming it compiles and builds correctly, the 64-bit operations would be done using 32-bit instructions and 32-bit CPU registers, making it slower and more inefficient, and losing the performance advantage that these algorithms have over other competing pseudorandom number generator algorithms.

So I would really like to see good 32-bit implementations of xorshift* and xorshift+ with appropriate state sizes and parameters for a, b, and c that maximize the randomness characteristics and also have good performance, as has been done already with the 64-bit implementations. The majority of software for personal computers is still 32-bit, even on 64-bit versions of Windows, and plenty of people with 64-bit processors have 32-bit operating systems that don't support 64-bit programs (primarily because 64-bit operating systems are only recommended if you are using at least 2 gigabytes of RAM, so if you have a 64-bit CPU and less RAM it's typically best to stick with a 32-bit OS). Any software that is trying to maximize its portability and compatibility with different platforms will probably be 32-bit. So having an algorithm that nobody's bothered to get working on 32-bit architectures makes it rather difficult for widespread use of this algorithm to catch on. For instance, the Mersenne Twister algorithm is quite widespread and popular now, despite being slower than xorshift* and xorshift+, having much worse randomness characteristics, and having an absurdly large state space, among other issues. But it is implemented for both 32-bit and 64-bit systems and anyone can easily find the code for it, which is public domain, and use it. For widespread adoption of a better pseudorandom number generator it has to be available in not just 64-bit but 32-bit too, with public domain code. The infamous RANDU linear congruential generator, which had TERRIBLE randomness characteristics, is still in use even today by some people, and it was used in numerous scientific simulations whose results were published in peer-reviewed journals, and whose results are now being called into question. In the name of Science we need to have good 32-bit implementations of xorshift* and xorshift+ so that widespread adoption of these, as replacements for earlier pseudorandom number generators that are vastly inferior, can be done and then scientific simulations will be much more accurate.

Yes, there are cryptograhically secure random number generators that are even more random, but due to their slower speed, oftentimes they are not an option, which is why this is rather important; also some of them have implementation details that are not publicly known, such as CryptGenRandom() or various hardware implementations such as Intel's, so they cannot have their properties analyzed mathematically in order to generate logical proofs of their level of cryptographic security, as has been done with Blum Blum Shub. There is still a need for good non-cryptographic pseudorandom number generators that work on 32-bit systems. And while George Marsaglia's original xorshift has a 32-bit implementation, its randomness characteristics are demonstrably worse than the popular Mersenne Twister so it is not really the solution, even if you give it a large state space such as 1024 or 4096 bits. I suppose that perhaps the MurmurHash3's finalization phase for 32-bit architectures might work for now as a good pseudorandom number generator on 32-bit systems (probably better than any other non-cryptographic pseudorandom number generator currently in use on 32-bit architectures, except for its short period), but it would be nice to have xorshift+ and xorshift* also on 32-bit architectures as an even better alternative (faster and more random, as well as a longer period). After all, if people were not concerned about speed, everyone would be using Blum Blum Shub. So xorshift* and xorshift+ are essential and need to be ported to more architectures and put into widespread use.

xoroshiro and xoshiro are successors of xorshift. In http://xoshiro.di.unimi.it there are four 32-bit generators given: xoroshiro64*, xoroshiro64**, xoshiro128+ and xoshiro128**. 2A01:119F:21E:4D00:D952:8390:9324:D3E (talk) 09:40, 8 June 2019 (UTC)

Either that or, perhaps we could try random number generators based on computing arbitrary digits of irrational numbers (or more specifically, normal numbers). Apparently there are formulae to compute arbitrary binary or hexadecimal digits of numbers like pi rapidly. This could be a promising source of randomness, and what's more, it would have infinite period. There's some debate as to whether the digits of pi are equidistributed, but there are provably normal numbers so we could just use those instead (although the provably normal numbers tend to just be provably normal in one base). But as far as I know there's been hardly any research into the feasibility of a random number generator based on the digits of an irrational number, and it has not been implemented by anyone either. --Yetisyny (talk) 10:00, 8 August 2014 (UTC)

If you need a small, fast, good noncryptographic prng you can try http://burtleburtle.net/bob/rand/smallprng.html; if you really need a 32 bit version of this, I guess your best option is to contact the author Useurandom (talk) 12:57, 8 August 2014 (UTC)

Vigna (talk) 18:19, 20 December 2015 (UTC)== Comparison to Mersenne Twister ==

Although this page claims that xorshift with some non-linear modifications passes many randomness tests, the Mersenne twister is still more widespread. Does anyone know of a comparison of features between the two and why xorshift is not more widespread (given its fast execution)? Wqwt (talk) 22:05, 23 August 2014 (UTC)

Vigna's paper ("An experimental exploration of Marsaglia's xorshift generators, scrambled", link in the article) compares them based on how they fare under TestU01/dieharder, how quickly they recover from an initial state with too few zero bits, and speed; the author provides the code (GPL) in case you want to rerun the experiments (I haven't). Re the minor diffusion, well, I can't tell for sure, but I guess it's mostly inertia - MT is very well known, both for its fame and mathematical properties, and good enough that people won't be looking for an alternative unless it turns out to be ASTONIGHINGLY better. Maybe it will just take some time :) Useurandom (talk) 13:00, 25 August 2014 (UTC)

I believe in the security industry lots of value is put on time-tested and widespread methods. The reluctance to switch away from MT seems to support this. Wqwt (talk) 01:37, 10 October 2014 (UTC)

Well, it takes some time but the industry is getting there: v8project.blogspot.it/2015/12/theres-mathrandom-and-then-theres.html. Vigna (talk) 18:19, 20 December 2015 (UTC)

Where did the example xorshift128 algorithm and parameters come from?

The example implementation of xorshift128 does not seem to match the recommended algorithm in Marsaglia's paper https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf

I've annotated with minor comments:

/* The state array must be initialized to not be all zero */
uint32_t xorshift128(uint32_t state[static 4])
{
	uint32_t t = state[3];
	t ^= t << 11;
	t ^= t >> 8;
	state[3] = state[2]; state[2] = state[1]; state[1] = state[0];
	t ^= state[0];
	t ^= state[0] >> 19;	
	state[0] = t;
	return t;
}

In Marsaglia's paper the iteration operation is listed as

t=(xˆ(x<<a)); x=y; y=z; z=w; return w=(wˆ(w>>c))ˆ(tˆ(t>>b));

with sample suitable values for (a,b,c) listed as (5,14,1), (15,4,21), (23,24,3), (5,12,29)

This has not only different parameters but a different structure. Where did the code in this article come from?

Arghman (talk) 16:23, 20 September 2017 (UTC)

This comes from the function called xor128 that Marsaglia gave in Summary section of the paper to compare it with MWC. Except that someone decided to rename it and refactor beyond recognition (it seems to be correct, though; it still has the same structure you cited if I'm not mistaken). Parameters (11,8,19) were used in Marsaglia's xor128, examples in section 3.1 are not exhaustive. — mwgamera (talk) 02:37, 23 September 2017 (UTC)

Daniel Lemire's findings that Xorshift128+ and Xorshift1024* fail BigCrush

Daniel Lemire has written several blog posts that dispute the claim on wikipedia that Xorshift128+ and Xorshift1024* pass the BigCrush statistical test: https://lemire.me/blog/2017/09/08/the-xorshift128-random-number-generator-fails-bigcrush/ https://lemire.me/blog/2017/09/15/the-xorshift1024-random-number-generator-fails-bigcrush/. Lemire has published his source code https://github.com/lemire/testingRNG/.

Note: I have made a small contribution to the above-named github repository. — Preceding unsigned comment added by JeffEpler (talk • contribs) 18:58, 3 November 2017 (UTC)

Xorwow code seems incorrect

It seems to me that the function xorwow() on the Wikipedia page is not equivalent to the code sample presented by Marsaglia on page 5 of his paper Xorshift RNGs.

The code in the paper is (initialization values left out for brevity):

 unsigned long xorwow() {
   static unsigned long x, y, z, w, v, d;
   unsigned long t = (x^(x>>2));
   x = y; y = z; z = w; w = v; v = (v^(v<<4))^(t^(t<<1));
   return (d += 362437) + v;
 }

Rewriting the xorwow() code from the Wikipedia page in the style of the paper, I get to:

 uint32_t xorwow() {
   static uint32_t y, z, w, v, d;
   uint32_t t = (y^(y>>2));
   y = z; z = w; w = v; v = (v^(v<<4))^(t^(t<<1));
   return (d += 362437) + v;
 }

The two functions above are similar but different. The first version (from the paper) uses a chain of 5 internal variables, while the second version (from the Wikipedia page) uses a chain of just 4 internal variables.

In addition, the Wikipedia page says the period of this generator is (2¹⁶⁰-2³²) while the paper says (2¹⁹²-2³²). (I guess both statements are true, but the statement on the Wikipedia page refers to an RNG different from the original Xorwow.)

I propose to change the code in the Wikipedia page to make it conform to the paper. For example:

struct xorwow_state {
  uint32_t x, y, z, w, v, d;
};

/* The state array must be initialized to not be all zero in the first four words */
uint32_t xorwow(struct xorwow_state *state)
{
    /* Algorithm "xorwow" from p. 5 of Marsaglia, "Xorshift RNGs" */
    uint32_t t = state->x;
    uint32_t v = state->v;
    state->x = state->y;
    state->y = state->z;
    state->z = state->w;
    state->w = state->v;
    t ^= t >> 2;
    v ^= (v << 4) ^ t ^ (t << 1);
    state->v = v;
    state->d += 362437
    return v + state->d;
}

JorisVR (talk) 09:13, 6 August 2020 (UTC)

Since nobody commented on this topic, I edited the Xorwow section of the article as proposed. JorisVR (talk) 14:36, 30 August 2020 (UTC)

xorwow() defect

I've documented a distribution defect in the lower 4 bits of the xorwow() RNG and posted a copy online via my personal website at

v-sonline.com/xorwow/xorwow_defect.txt

I've already sent copies to the NVidia developers contact portal and to TestU01 via simul@iro.umontreal.ca today.

Aside from avoiding the use of lower 4 bits of xorwow(), whoever knows who to contact to get this fixed and possibly to add another test for randomness to the existing suite of tests, please do. If this report text needs to be included here, my permission is given to do so. Youjaes (talk) 00:48, 18 February 2023 (UTC)

As an observation, the state->counter increments by 362437, an odd number, so it's least significant bit 'blinks' 1,0,1,0... Youjaes (talk) 06:08, 21 February 2023 (UTC)