在Java和Python中實現XorShift相同

Question

我想在Java，Python和JavaScript中實現XorShift PRNG。不同的實現必須在給定相同種子的情況下生成完全相同的序列。到目前爲止，我一直無法做到這一點。

我在Java中實現

具有以下實現的XorShift PRNG在Java中（其中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。以下是使用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庫實現移植到其他語言，儘管它不是很好。

• 我可以修復我的上述實施，以便他們工作嗎？
• 我應該切換到另一個PRNG函數，它更容易在prog.langs中實現嗎？

我讀過SO，其中有人建議使用Python的java.util.Random類。我不想要這個，因爲我也需要JavaScript中的函數，而且我不知道這個包在那裏存在。

Answer 1

我很高興回答這個問題，讓我用這三種語言編寫PRNG，而且速度很快。它不一定非常好。

您可以使用3種語言實現32位linear congruential generator。

的Python：

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

的Java：

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) 

需要那些醜陋的shift值，以防止NumPy發出奇怪的鑄造錯誤。在任何情況下，這將產生完全相同的結果是你的Java版本：

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

Answer 3

在Java和Python之間的結果的差異是由於在如何語言已經實現整數的差異。一個java long是一個64位有符號整數，在最左邊的位有符號。 Python是......好吧，不同。

推測蟒編碼整數具有變化取決於

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

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

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

和負整數（可能）編碼爲符號和大小的數的大小的比特長度，雖然符號似乎沒有任何要被設置的位。標誌通常在最左邊，但不在這裏。我想這與蟒蛇不同的數字長度有關。

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

其中-4在64位補是：

0b1111111111111111111111111111111111111111111111111111111111111100 

這使得算法中的巨大差異，因爲換擋0b100時向左或向右的產量相當不同的結果不是轉移0b1111111111111111111111111111111111111111111111111111111111111100。

幸運的是，有一種欺騙python的方法，但這涉及到自己在兩個表示之間切換。需要

首先，一些位掩碼：

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

我們迫使蟒成2的補碼，都是一個需要的是一個合乎邏輯的「和」字掩蓋

>>> 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位，數字環繞。我還沒有進一步調查。