xorshift 及其变体在 C 中给出非随机结果

Question

我正在尝试创建一个伪随机生成器 API，但是 xorshift 生成的数字具有非随机性。您可以在此处查看算法和测试：

#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;
}

我面临的问题是上面测试的输出：

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

我知道 xorshift 的某些版本在较高 and/or 低位方面存在问题，但我尝试了此处描述的所有变体（包括 CUDA 版本）：https://en.wikipedia.org/wiki/Xorshift，并且所有变体都给出了预测结果. 错误在哪里？对于这种任务，是否有任何替代方案（线性同余 RNG 除外）？

Answer 1

您正在查看在 0 和 18,446,744,073,709,551,615 (UINT64_MAX) 之间均匀分布的随机数。 10,000,000,000,000,000,000 和 18,446,744,073,709,551,615 之间的所有数字都以 1 开头，因此偏态分布是意料之中的。

xorshift 及其变体在 C 中给出非随机结果

xorshift and its variations give unrandom results in C

c

random

algorithm

xor