lundi 14 juin 2021

xorshift and its variations give unrandom results in C

I'm trying to create a pseudo-random generator API, but numbers generated by xorshift have unrandom nature. You can see the algorithm and tests here:

#include <stdio.h>
#include <stdlib.h>
 
/* basic random stream structure */
typedef struct Random64 {
    uint64_t seed;
    uint64_t current;
} Random64;
 
/* returns a new stream of uint64_t values */
Random64 new_rand64(uint64_t seed) {
    Random64 new_stream;
 
    if (seed == 0) {
        perror("SEED MUST BE A NON-ZERO VALUE");
    }
 
    new_stream.seed = new_stream.current = seed;
    return new_stream;
}
 
/* returns the next random value from sequence initialized with seed */
uint64_t next64(Random64* stream) {
    uint64_t cur = stream->current;
    cur ^= cur << 13;
    cur ^= cur >> 35;
    cur ^= cur << 30;
 
    return stream->current = cur;
}
 
/* returns the first digit of given number */
uint64_t get_first_digit(uint64_t num) {
    while (num >= 10) {
        num /= 10;
    }
 
    return num;
}
 
/* returns the last digit of given number */
uint64_t get_last_digit(uint64_t num) {
    return num % 10;
}
 
int main(void) {
    Random64 stream = new_rand64(12358101632999);
 
    uint64_t lasts[10] = {0};
    uint64_t firsts[10] = {0};
 
    /* test */
    for (int i = 0; i < 100000; ++i) {
        uint64_t val = next64(&stream);
 
        ++lasts[get_last_digit(val)];
        ++firsts[get_first_digit(val)];
    }
 
    /* print all last digits */
    for (int i = 0; i < 10; ++i) {
        printf("Last %d occurs %llu times\n", i, lasts[i]);
    }
 
    putchar('\n');
 
    /* print all first digits */
    for (int i = 0; i < 10; ++i) {
        printf("First %d occurs %llu times\n", i, firsts[i]);
    }
 
    return 0;
}

The problem I'm facing is this output from my test above:

Last 0 occurs 9925 times
Last 1 occurs 9976 times
Last 2 occurs 9799 times
Last 3 occurs 10042 times
Last 4 occurs 10056 times
Last 5 occurs 9942 times
Last 6 occurs 10281 times
Last 7 occurs 9913 times
Last 8 occurs 10107 times
Last 9 occurs 9959 times

First 0 occurs 0 times
First 1 occurs 51813 times   < "one" occurs almost 9 times more than other numbers
First 2 occurs 6036 times
First 3 occurs 5909 times
First 4 occurs 6081 times
First 5 occurs 6122 times
First 6 occurs 5993 times
First 7 occurs 6103 times
First 8 occurs 5936 times
First 9 occurs 6007 times

I know that some versions of xorshift have troubles with higher and/or lower bits, but I tried all variations (including CUDA's version) described here: https://en.wikipedia.org/wiki/Xorshift, and ALL of them give predictive results. Where is the mistake? Are there any alternatives (except linear congruential RNGs) for this kind of task?




Aucun commentaire:

Enregistrer un commentaire