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