xorshift128 +算法的真正定义是什么？ [英] What is the real definition of the xorshift128+ algorithm?

问题描述

我需要一个好的伪随机数生成器（PRNG），似乎当前的最新技术是xorshift128 +算法。不幸的是，我发现了2个不同的版本。维基百科上的一个： Xorshift 显示为：

I have need of a good pseudo random number generator (PRNG), and it seems like the current state of the art is the xorshift128+ algoritm. Unfortunately, I have discovered 2 different versions. The one on wikipedia: Xorshift shows as:

uint64_t s[2];

uint64_t xorshift128plus(void) {
    uint64_t x = s[0];
    uint64_t const y = s[1];
    s[0] = y;
    x ^= x << 23; // a
    s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
    return s[1] + y;
}

这似乎很简单。而且，编辑日志似乎显示此代码段是由名为 Vigna的用户添加的，该用户大概是 Sebastiano Vigna，他是xorshift128 +上论文的作者：对Marsaglia的xorshift生成器进行进一步加扰。不幸的是，该论文中的实现略有不同：

Which seems straight forward enough. What's more, the edit logs appear to show that this code snippet was added by a user named "Vigna", which is presumably "Sebastiano Vigna" who is the author of the paper on xorshift128+: Further scramblings of Marsaglia’s xorshift generators. Unfortunately, the implementation in that paper is slightly different:

uint64_t next(void) {
    uint64_t s1 = s[0];
    const uint64_t s0 = s[1];
    s[0] = s0;
    s1 ^= s1 << 23; // a
    s[1] = s1 ^ s0 ^ (s1 >> 18) ^ (s0 >> 5); // b, c
    return s[1] + s0;
}

除了一些不同的名称外，这两个摘要是相同的，除了最后两个转移。在Wikipedia版本中，这些偏移分别为17和26，而论文中的偏移为18和5。

Apart from some different names, these two snippets are identical except for the final two shifts. In the Wikipedia version those shifts are by 17 and 26, while the shifts in the paper are by 18 and 5.

有人知道哪个是正确的算法吗？这有什么不同吗？显然，这是一种使用相当广泛的算法-但使用的是哪个版本？

Does anyone know which is the "right" algorithm? Does it make a difference? This is apparently a fairly widely used algorithm - but which version is used?

推荐答案

感谢@Blastfurnace，看来答案是根据算法作者的说法，最新的常量集是：23、18和5。显然，这没什么大不了的，但是从理论上讲，这些常量要比他使用的初始数字更好。 Sebastiano Vigna针对新闻显示V8 Javascript引擎正在转向使用此算法。

Thanks to @Blastfurnace, it appears that the answer is that the most recent set of constants according to the author of the algorithm are: 23, 18, and 5. Apparently it doesn't matter too much, but those are theoretically better than the initial set of numbers he used. Sebastiano Vigna made these comments in response to the news that the V8 Javascript engine is shifting to using this algorithm.

我正在使用的实现是：

uint64_t a = s[0];
uint64_t b = s[1];

s[0] = b;
a ^= a << 23;
a ^= a >> 18;
a ^= b;
a ^= b >>  5;
s[1] = a;

return a + b;

这篇关于xorshift128 +算法的真正定义是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！