XorShift implementation is the same in Java and Python

Question

I would like to implement XorShift PRNG in Java, Python and JavaScript. Different implementations must generate exact sequences defined by the same seed. So far, I have not been able to do this.

My implementation in Java

have the following implementation of XORShift PRNG in Java (where xis this field long):

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

If I run xat 1, the first four calls randomLong()will generate:

35651601
1130297953386881
-9204155794254196429
144132848981442561

My Python implementation

I have tried both with and without numpy. Below is the version using 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

With the same seed, the Python function will generate:

35651601
1130297953386881
-9204155787274874573 # different
143006948545953793   # different

My JavaScript implementation

I have not tried to use it yet, because the JavaScript number type seems to double based on IEEE 754, which opens up a different can of worms.

I think the reason

Java Python . Java 32 64- , Python int.

, . , Java , , Python (?).

, PRNG , . . C libs , .

• , ?
• PRNG, prog.langs?

SO, - java.util.Random Python. , JavaScript, , .

Answer 1

, PRNG , . .

32- .

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

, 32- .

Answer 2

. Python, NumPy, 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 . , , 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'

-4 64 2 :

0b1111111111111111111111111111111111111111111111111111111111111100

, 0b100 , 0b1111111111111111111111111111111111111111111100.

, , .

-:

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

, python 2 , , , - "" mask

>>> 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, , .

I could not implement the same algorithm in JavaScript. It seems that JavaScript uses 32-bit unsigned integers and an offset of 35 positions to the right, the number wraps around. I have not explored it yet.