寻找逆运算乔治马尔萨利亚的XorShift RNG [英] Finding inverse operation to George Marsaglia's XorShift RNG
问题描述
摘要
假设你有128位自动机（再由四个32位字 X ，是ž，>，<$ C $ W ）是根据以下规则改变它的状态：
X = ...
Y = ...
Z = ...
W = ...
接下来无效（）
{
VAR T = X ^（X＆LT;＆LT; 11）;
X = Y;
Y = Z;
Z =瓦;
W =W¯¯^（并且R w＆GT; 19）^（吨^（吨＆GT;→8））;
}
^ - 表示二进制 XOR 操作
＆LT;＆LT; - 表示二进制左移操作
＆GT;＆GT; - denotys二元右移操作
这是保证上面的自动机不产生冲突，即每个状态是一个（也是唯一一个）previous状态的结果。这也保证了上述状态机产生2 ^ 128个不同的国家。
问题
对于任何给定的状态（X，Y，Z，W）产生逆下一步，（即 $ P $光伏）的操作，将恢复状态，以previous之一。
在换句话说，如果你有下列情形（X = 1，Y = 2，Z = 3，W = 4）并调用接下来，国家将改为（X = 2，Y = 3，Z = 4，W = 2061），它应该在调用后 $ P $光伏国家应再次等于（X = 1，Y = 2，Z = 3，W = 4） 。
P.S。
在接下来的操作是发现了乔治马尔萨利亚
https://en.wikipedia.org/wiki/Xorshift
逆这一操作将是一般非常有用的，可以考虑Guid.Next（...），GUID。preV（...）的可用性
的影响修改
我已经有所改善尼克拉斯·B.原来的答案，并移植结果C＃，所以这里的最后一张code，希望有人会从Random.Next（）和随机受益。preV（）操作：
公共部分类Xor128
{
公共UInt32的X {获得;组; }
公共UInt32的ÿ{获得;组; }
公共UInt32的ž{获得;组; }
公共UInt32的W {获得;组; }
公共Xor128（）
：这个（Guid.NewGuid（））
{
}
公共Xor128（GUID GUID）
{
GUID = GUID;
}
公共Xor128（byte []的字节）
{
字节=字节;
}
公共Xor128（UInt32的X，UInt32的Y，UInt32的Z，UInt32的W）
{
X = X;
Y = Y;
Z = Z者除外;
W =瓦;
InitZiggurat（）;
}
公共字节[]字节
{
得到
{
VAR字节=新字节[16];
VAR手柄= GCHandle.Alloc（字节，GCHandleType.Pinned）;
尝试
{
变种PTR = handle.AddrOfPinnedObject（）;
Marshal.WriteInt32（PTR，为0x0，（Int32）已X）;
Marshal.WriteInt32（PTR，为0x4，（Int32）在Y）;
Marshal.WriteInt32（PTR，0x8中，（Int32）在Z）;
Marshal.WriteInt32（PTR，位于0xC，（Int32）在W）;
}
最后
{
handle.Free（）;
}
返回字节;
}
组
{
如果（value.Length＆GT; = 16）{
VAR手柄= GCHandle.Alloc（值，GCHandleType.Pinned）;
尝试 {
变种PTR = handle.AddrOfPinnedObject（）;
X =（UInt32的）Marshal.ReadInt32（PTR，为0x0）;
Y =（UInt32的）Marshal.ReadInt32（PTR，为0x4）;
Z =（UInt32的）Marshal.ReadInt32（PTR，位于0x8）;
W =（UInt32的）Marshal.ReadInt32（PTR，位于0xC）;
} 最后 {
handle.Free（）;
}
InitZiggurat（）;
} 其他 {
抛出新ArgumentOutOfRangeException（）;
}
}
}
公众的Guid的Guid
{
得到
{
返回新的GUID（字节）;
}
组
{
字节= value.ToByteArray（）;
}
}
私人UInt32的UnXorShl（UInt32的X，的Int32移）
{
对于（VAR I =移; I＆LT; 32; I＆LT;＆LT; = 1）X ^ = X＆LT;＆LT;一世;
返回X;
}
私人UInt32的UnXorShr（UInt32的X，的Int32移）
{
对于（VAR I =移; I＆LT; 32; I＆LT;＆LT; = 1）X ^ = X＆GT;＆GT;一世;
返回X;
}
公共UInt32的preV（）{
VAR T = UnXorShr（W ^ Z ^（Z＆GT;＆GT; 19），8）;
W = Z者除外;
Z =ÿ;
Y = X;
X = UnXorShl（T，11）;
返回瓦;
}
公共UInt32的币种（）{
返回瓦;
}
公共UInt32的下一个（）
{
UInt32的T = X ^（X＆LT;＆LT; 11）;
X = Y;
Y = Z;
Z =瓦;
返回W¯¯= W ^（并且R w＆GT; 19）^（吨^（吨＆GT;→8））;
}
}
您需要的基本构建模块是一个算法来扭转左移位操作 F（X）= X ^（X＆LT的XOR ;＆LT; S）一段S> 0。由于F（X），你已经知道x的直接低s位。
您可以重建的迭代位由低到高的休息，因为你已经知道在每个点已经XOR运算得到F（X）的位的两位。下面是在Python的例子：
高清reverse_xor_lshift（Y，转移，W = 32）：
X = Y＆放大器; （（1＆其中;＆所述;移） - 1）
因为我在范围内（W - 转移）：
X | =（1，如果布尔（X及（1＆其中;＆所述; i））的^布尔（γ及（1＆其中;≤（移+ i））的）其他0）其中;≤（移+ i）产品
返回X
现在剩下变得相当容易。请注意，我再利用左移逆转为右移模拟：
高清reverse_bin（X，W = 32）：
返回INT（仓（x）的[2：]。rjust（瓦特，'0'）[:: - 1]，2）
高清reverse_xor_rshift（Y，转移，W = 32）：
＃为简单起见，我们只重用reverse_xor_lshift这里
返回reverse_bin（reverse_xor_lshift（reverse_bin（Y），移））
高清向前（X，Y，Z，W）：
吨=（X ^（X LT;＆所述; 11））及为0xffffffff
X = Y
Y = Z
ž= W
W =W¯¯^（并且R w＆GT; 19）^（吨^（吨＆GT;→8））
返回（X，Y，Z，W）
高清向后（X，Y，Z，W）：
T = reverse_xor_rshift（W ^ Z ^（Z＆GT;＆GT; 19），8）
返回（reverse_xor_lshift（吨，11）中，X，Y，Z）
后退是颠倒的状态转换的功能。一些随机测试：
导入随机
对于_范围内（1000）：
的X，Y，Z，W = [random.randint（0,2 ** 32-1），用于在_范围（4）]
断言向后（向前*（X，Y，Z，W））==（X，Y，Z，W）
似乎工作。
Abstract
Hi, suppose you have 128 bit automata (represented by four 32 bit words X, Y, Z, W) that changes it's state according to a following rule:
X = ...
Y = ...
Z = ...
W = ...
void next()
{
var t = X ^ (X << 11);
X = Y;
Y = Z;
Z = W;
W = W ^ (W >> 19) ^ (t ^ (t >> 8));
}
^ - denotes binary XOR operation
<< - denotes binary shift left operation
>> - denotys binary shift right operation
It is guaranteed that the above automata generates no collisions i.e. each state is a result of one (and only one) previous state. It is also guaranteed that the above state machine produces 2^128 unique states.
Question
For any given state (X,Y,Z,W) produce inverse to next, (i.e. prev) operation that would revert the state to previous one.
In other words, if you have the following state (X=1, Y=2, Z=3, W=4) and will call next, the state will change to (X=2, Y=3, Z=4, W=2061), it is supposed that after calling prev the state should be equal again to (X=1, Y=2, Z=3, W=4).
P.S.
The next operation is one of the implementations to XorShift pseudorandom number generators that was discovered by George Marsaglia
https://en.wikipedia.org/wiki/Xorshift
The inverse to this operation would be very useful in general, consider the implications of Guid.Next(...), Guid.Prev(...) availability
Edit
I have somewhat improved Niklas B.'s original answer and ported result to C#, so here's the final piece of code, hope someone will benefit from Random.Next() and Random.Prev() operations:
public partial class Xor128
{
public UInt32 X { get; set; }
public UInt32 Y { get; set; }
public UInt32 Z { get; set; }
public UInt32 W { get; set; }
public Xor128()
: this(Guid.NewGuid())
{
}
public Xor128 (Guid guid)
{
Guid = guid;
}
public Xor128(byte[] bytes)
{
Bytes = bytes;
}
public Xor128(UInt32 x, UInt32 y, UInt32 z, UInt32 w)
{
X = x;
Y = y;
Z = z;
W = w;
InitZiggurat();
}
public byte[] Bytes
{
get
{
var bytes = new byte[16];
var handle = GCHandle.Alloc(bytes, GCHandleType.Pinned);
try
{
var ptr = handle.AddrOfPinnedObject();
Marshal.WriteInt32(ptr, 0x0, (Int32)X);
Marshal.WriteInt32(ptr, 0x4, (Int32)Y);
Marshal.WriteInt32(ptr, 0x8, (Int32)Z);
Marshal.WriteInt32(ptr, 0xC, (Int32)W);
}
finally
{
handle.Free();
}
return bytes;
}
set
{
if (value.Length >= 16) {
var handle = GCHandle.Alloc (value, GCHandleType.Pinned);
try {
var ptr = handle.AddrOfPinnedObject ();
X = (UInt32)Marshal.ReadInt32 (ptr, 0x0);
Y = (UInt32)Marshal.ReadInt32 (ptr, 0x4);
Z = (UInt32)Marshal.ReadInt32 (ptr, 0x8);
W = (UInt32)Marshal.ReadInt32 (ptr, 0xC);
} finally {
handle.Free ();
}
InitZiggurat ();
} else {
throw new ArgumentOutOfRangeException ();
}
}
}
public Guid Guid
{
get
{
return new Guid (Bytes);
}
set
{
Bytes = value.ToByteArray ();
}
}
private UInt32 UnXorShl(UInt32 x, Int32 shift)
{
for (var i = shift; i < 32; i <<= 1) x ^= x << i;
return x;
}
private UInt32 UnXorShr(UInt32 x, Int32 shift)
{
for (var i = shift; i < 32; i <<= 1) x ^= x >> i;
return x;
}
public UInt32 Prev() {
var t = UnXorShr (W ^ Z ^ (Z >> 19), 8);
W = Z;
Z = Y;
Y = X;
X = UnXorShl (t, 11);
return W;
}
public UInt32 Curr() {
return W;
}
public UInt32 Next()
{
UInt32 t = X ^ (X << 11);
X = Y;
Y = Z;
Z = W;
return W = W ^ (W >> 19) ^ (t ^ (t >> 8));
}
}
The basic building block you need is an algorithm to reverse the XOR with left shift operation f(x) = x ^ (x << s) for some s > 0. Given f(x), you already know the lower s bits of x directly.
You can reconstruct the rest of the bits iteratively from low to high, because you already know at each point the two bits that have been XORed to get the bit of f(x). Here's an example in Python:
def reverse_xor_lshift(y, shift, w=32):
x = y & ((1<<shift) - 1)
for i in range(w - shift):
x |= (1 if bool(x & (1<<i)) ^ bool(y & (1<<(shift+i))) else 0)<<(shift+i)
return x
Now the rest becomes rather easy. Note that I'm reusing the left shift reversal for the right shift analogue:
def reverse_bin(x, w=32):
return int(bin(x)[2:].rjust(w, '0')[::-1], 2)
def reverse_xor_rshift(y, shift, w=32):
# for simplicity, we just reuse reverse_xor_lshift here
return reverse_bin(reverse_xor_lshift(reverse_bin(y), shift))
def forward(X, Y, Z, W):
t = (X ^ (X << 11)) & 0xffffffff
X = Y
Y = Z
Z = W
W = W ^ (W >> 19) ^ (t ^ (t >> 8))
return (X, Y, Z, W)
def backward(X, Y, Z, W):
t = reverse_xor_rshift(W ^ Z ^ (Z >> 19), 8)
return (reverse_xor_lshift(t, 11), X, Y, Z)
backward is the function that reverses the state transition. Some random testing:
import random
for _ in range(1000):
X, Y, Z, W = [random.randint(0,2**32-1) for _ in range(4)]
assert backward(*forward(X,Y,Z,W)) == (X, Y, Z, W)
Seems to work.
这篇关于寻找逆运算乔治马尔萨利亚的XorShift RNG的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
