non-uniform distribution of wyrand() about wyhash HOT 4 CLOSED

Correct. I do not think it is a bijection so, indeed, if you try to generate 2^64 values, some values will occur more than once. However, 2^64 is an enormous number.

from wyhash.

Dear yuriev:
This good question has been discussed in a numpy thread. I would like to give a few commnets:

1: wyrand is too simple to be analyzed. it takes a 64 bit seed and return 64bit random number. This raised the question of bijection. In fact other PRNG uses 256 bit states/seed and return 64 bit random number. thus bijection is not a requirement of a valid PRNG. Or many valid PRNGs on the market is not bijective.

2: bijection is not good for PRNG. suppose we have a 3 bit PRNG, and it return 8 distinct numbers at 8 calls. When I am gambling, if I see the previous 7 numbers, the 8th number is determined with bijection assumption, I can bet all my money on the rest number.

3: when I do 2^64 sampling, it is natural to have 37% duplicate numbers. This is called "bootstrap" in statistics. zero duplicate is not a natral/random observation.

4: the BigCrush designers have better knowledge on statistical randomness than us. They work hard in order to crush poor PRNGs. We need to trust them. If bijection can be exploited, these guys will already do that for sure.

5: the last, you can test other modern PRNGs on the market, they will behave like wyrand in a statistical sense, eg. ~40% 16 bit duplicates.

I hope you are satisfied with my simple explainations.

Yours,
Yi

from wyhash.

Dear yuriev:
My additional thought confirms your worry. maybe I should restate that:
wyrand is of 32-bit strength/randomness

as wyrand's internal state is 64 bit, I guess it only has 32-bit randomness (something similar to birthday attack in hash). And BigCrush in fact is a 32-bit test. So if we trust BigCrush, we can at least claim 32-bit randomness.

However, I am not going return unsigned for wyrand, 64 bit return is still useful. But we should not apply it to large space, as some 64-bit numbers will never be generated.

Thank you very much! I am going to design a full 64-bit PRNG with 128-bit internal states.

from wyhash.

since mum is symmetrical, the entropy of wyrand() is at most 63. it is easy to find pair of seeds to return same first results:

	uint64_t seed_a = time(NULL);
	uint64_t seed_b = ((seed_a + _wyp[0]) ^ _wyp[1]) - _wyp[0];

But this do not influence the distribution of the output sequence. The real problem should be the internal state period has the nearly same bits with the output, so theoretically we could recover the all following sequence of 64-bit strings by just observing 2 iterations.

from wyhash.