xoshiro / xoroshiro and zero

Viewed 685

Is xoshiro / xoroshiro pseudo-random number generator able to generate zero, if it is properly seeded? Does it generate zero with the same probability as other values?

2 Answers

These generators cannot have an all-zero state, but they can produce zeroes when they collapse the state to produce an output. This doesn't have anything to do with "proper" seeding, distributional properties are characteristics that emerge over the course of a PRNG's cycle while the seed state is just the point at which you enter the cycle.

I think the following section from the page you linked to contains your answer regarding probabilities of zeros:

Equidistribution

Every 64-bit generator of ours with n bits of state scrambled with * or ** is n/64-dimensionally equidistributed: every n/64-tuple of consecutive 64-bit values appears exactly once in the output, except for the zero tuple (and this is the largest possible dimension). Generators based on the + scrambler are however only (n/64 − 1)-dimensionally equidistributed: every (n/64 − 1)-tuple of consecutive 64-bit values appears exactly 264 times in the output, except for a missing zero tuple. The same considerations apply to 32-bit generators.

It looks like zero occurs marginally less often than all other values to the tune of one part in 264, so technically it has a different probability. Practically speaking I'd say that makes no difference.

Answer is yes.

You could look at the code as well. F.e., if you look at, say, Xoroshiro128+ source, you could see that as soon as sum of s0 and s1 is equal to 264, then returned result would be 0 (result is sum mod 264). You could even seed it in such way that first Xoroshiro128+ output would be zero, see code below. If we assume that internally s0 and s1 are perfectly chopped and bit patterns are equiprobable (well, they are intermixed together so this is not quite true), then 0 appears marginally less probable than than all other values, as @pjs noted (when s0 is 0 you'll never get 0 RNG output, true for s1=0 as well). You could do similar analysis for other Vigna RNGs. Code

#include <stdio.h>
#include <stdint.h>
#include <limits.h>

static inline uint64_t rotl(const uint64_t x, int k) {
    return (x << k) | (x >> (64 - k));
}

static uint64_t s[2];

void seed(const uint64_t s0, const uint64_t s1) {
    s[0] = s0;
    s[1] = s1;
}

uint64_t next(void) {
    const uint64_t s0 = s[0];
    uint64_t s1 = s[1];
    const uint64_t result = s0 + s1;

    s1 ^= s0;
    s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16); // a, b
    s[1] = rotl(s1, 37); // c

    return result;
}

int main(void) {
    uint64_t s0 = 10446744073709551615ULL;
    uint64_t s1 = ULLONG_MAX - s0;

    seed(s0, s1 + 1); // or seed(s0 + 1, s1);

    uint64_t r;
    r = next();  printf("%llu\n", r);
    r = next();  printf("%llu\n", r);
    r = next();  printf("%llu\n", r);

    return 0;
}
Related