用Java和Python实现同样的XorShift

Question

我想用XorShift、实现一个Java。不同的实现必须生成完全相同的序列，给定相同的种子。到目前为止，我还没有做到这一点。

在Java中实现

在Java中有以下XorShift PRNG实现(其中x是long字段)：

public long randomLong() {
    x ^= (x << 21);
    x ^= (x >>> 35);
    x ^= (x << 4);
    return x;
}

如果我将x种子为1，那么对randomLong()的前四个调用将生成：

35651601
1130297953386881
-9204155794254196429
144132848981442561

用Python实现

我已经尝试过了，不管有没有裸皮。下面是使用numpy的版本。

def randomLong(self):
    self.x ^= np.left_shift(self.x, 21)
    self.x ^= np.right_shift(self.x, 35)
    self.x ^= np.left_shift(self.x, 4)
    return self.x

使用相同的种子，Python函数将生成：

35651601
1130297953386881
-9204155787274874573 # different
143006948545953793   # different

我的JavaScript实现

我还没有尝试过，因为JavaScript的唯一数字类型似乎是基于IEEE 754的双倍类型，这就打开了一个不同的蠕虫罐。

我认为原因是

Java和Python有不同的数字类型。Java有32位整数和64位整数，而Python有古怪的大int类型。

移位操作符似乎有不同的语义。例如，在Java中有逻辑移位和算术转移，而在Python中只有一种移位(逻辑？)。

问题

我会很高兴有一个答案，让我用这三种语言写一个PRNG，而且一个是快速的。它不一定要很好。我已经考虑过将C实现移植到其他语言，尽管它不是很好。

• 我能修复我的上述实现以便它们工作吗？
• 我应该切换到另一个更易于跨prog.langs实现的PRNG函数吗？

我读过有人建议对Python使用java.util.Random类的SO。我不想这样做，因为我也需要JavaScript中的函数，而且我也不知道这个包是否存在。

Answer 1

我会很高兴有一个答案，让我用这三种语言写一个PRNG，而且一个是快速的。它不一定要很好。

您可以用3种语言实现32位线性同余发生器。

Python：

seed = 0
for i in range(10):
    seed = (seed * 1664525 + 1013904223) & 0xFFFFFFFF
    print(seed)

爪哇：

int seed = 0;
for (int i = 0; i < 10; i++) {
    seed = seed * 1664525 + 1013904223;
    System.out.println(seed & 0xFFFFFFFFL);
}

JavaScript：

var seed = 0;
for (var i = 0; i < 10; i++) {
    // The intermediate result fits in 52 bits, so no overflow
    seed = (seed * 1664525 + 1013904223) | 0;
    console.log(seed >>> 0);
}

输出：

1013904223
1196435762
3519870697
2868466484
1649599747
2670642822
1476291629
2748932008
2180890343
2498801434

注意，在所有3种语言中，每次迭代都会打印一个无符号的32位整数。

Answer 2

棘手之处在于逻辑上的右移。如果您能够访问NumPy，在Python中最简单的操作是将x存储为uint64值，这样算术和逻辑右移操作是完全相同的，并在返回之前将输出值转换为int64，例如：

import numpy as np

class XorShiftRng(object):
    def __init__(self, x):
        self.x = np.uint64(x)

    def random_long(self):
        self.x ^= self.x << np.uint64(21)
        self.x ^= self.x >> np.uint64(35)
        self.x ^= self.x << np.uint64(4)
        return np.int64(self.x)

为了防止NumPy发出奇怪的转换错误，需要对shift值进行丑陋的转换。无论如何，这会产生与Java版本完全相同的结果：

>>> rng = XorShiftRng(1)
>>> for _ in range(4):
...     print(rng.random_long())
...
35651601
1130297953386881
-9204155794254196429
144132848981442561

Answer 3

Java和python结果的差异是由于语言实现整数的方式不同造成的。java long是一个64位有符号整数，其符号位于最左边位。Python是..。嗯，不一样。

据推测，python编码的整数具有不同的位长，取决于数字的大小。

>>> n = 10
>>> n.bit_length()
4

>>> n = 1000
>>> n.bit_length()
10

>>> n = -4
>>> n.bit_length()
3

负整数(大概)编码为符号和大小，尽管符号似乎没有在任何位中设置。标志通常在最左边，但不在这里。我想这与蟒蛇在数位长度上的变化有关。

>>> bin(-4)
'-0b100'

在64位第2位的补充中，其中-4将是：

0b1111111111111111111111111111111111111111111111111111111111111100

这在算法上产生了巨大的不同，因为移动0b100左右产生的结果与移位的0b1111111111111111111111111111111111111111111111111111111111111100.完全不同。

幸运的是，有一种欺骗python的方法，但这涉及到自己在这两个表示之间切换。

首先，需要一些比特掩码：

word_size = 64
sign_mask = 1<<(word_size-1)
word_mask = sign_mask | (sign_mask - 1)

现在，要强迫python成为2的补码，唯一需要的就是使用单词掩码的逻辑'and‘。

>>> bin(4 & word_mask)
'0b100'

>>> bin(-4 & word_mask)
'0b1111111111111111111111111111111111111111111111111111111111111100'

这就是算法工作所需要的。除非您需要在返回值时将数字转换回来，因为

>>> -4 & word_mask
18446744073709551612L

因此，这个数字需要从2的补码转换为符号大小：

>>> number = -4 & word_mask
>>> bin(~(number^word_mask))
'-0b100'

但这只适用于负整数：

>>> number = 4 & word_mask
>>> bin(~(number^word_mask))
'-0b1111111111111111111111111111111111111111111111111111111111111100'

由于应该按原样返回正整数，所以这样做更好：

>>> number = -4 & word_mask
>>> bin(~(number^word_mask) if (number&sign_mask) else number)
'-0b100'

>>> number = 4 & word_mask
>>> bin(~(number^word_mask) if (number&sign_mask) else number)
'0b100'

所以我实现了这样的算法：

class XORShift:
    def __init__(self, seed=1, word_length=64):
        self.sign_mask = (1 << (word_length-1))
        self.word_mask = self.sign_mask | (self.sign_mask -1)
        self.next = self._to2scomplement(seed)

    def _to2scomplement(self, number):
        return number & self.word_mask

    def _from2scomplement(self, number):
        return ~(number^self.word_mask) if (number & self.sign_mask) else number

    def seed(self, seed):
        self.next = self._to2scomplement(seed)

    def random(self):
        self.next ^= (self.next << 21) & self.word_mask
        self.next ^= (self.next >> 35) & self.word_mask
        self.next ^= (self.next <<  4) & self.word_mask
        return self._from2scomplement(self.next)

并将其与1一起播种，该算法返回其4个第一个数字：

>>> prng = XORShift(1)
>>> for _ in range(4):
>>>     print prng.random()

35651601
1130297953386881
-9204155794254196429
144132848981442561

当然，您可以通过使用numpy.int64免费获得这些信息，但是这并不那么有趣，因为它隐藏了原因的差异。

我无法在JavaScript中实现相同的算法。似乎JavaScript使用了32位无符号整数和移动的35个位置--右转--这个数字环绕在周围。我还没有进一步调查。