Squares RNG 64bit implementation differs from paper

[tridao]

Hi,

I was just reading the Squares RNG implementation here and it seems to differ from the paper.

In round 4, the paper has

t = x * x + z;
x = t;
x = (x >> 32) | (x << 32);
// t is then used to xor with the result of round 5

However, in the code here,

OpenRAND/include/openrand/squares.h

Line 138 in ba9fec3

x = round(x, z);

you have

x = round(x, z);  // i.e. x = x * x + z; x = (x >> 32) | (x << 32);
// x is then used to xor with the result of round 5

So the difference is that the paper uses t to xor while the code uses (t >> 32) | (t << 32) to xor.

[Shihab-Shahriar]

Hi @tridao, thanks for bringing this to our attention. And you're absolutely correct, this is a bug. I think it's a bit interesting that this RNG still managed to pass practrand and testU01 battery of statistical tests.

One thing to note, and perhaps I should make it more explicit in the doc, please don't use 64bit seed with this particular implementation of Squares. Squares algorithm requires the key (i.e. seed here) to have certain properties (e.g. "The key should be an irregular bit pattern with roughly half ones and
half zeros"), whereas we wanted to allow developers to use any unique integer as seed, and the hashing we use to solve this forced us to trim down seed.

[tridao]

Yup I saw that the seed is uint32_t and you need extra processing. Thanks!